草庐IT

java - 我对空间复杂度的分析是否正确？

coder 2024-03-29 原文

这是 Cracking the Coding Interview 5th edition 中的问题 9.5

问题:编写一个方法来计算一个字符串的所有排列

这是我的解决方案，用 Java 编码(测试它，它有效:))

public static void generatePerm(String s) {
    Queue<Character> poss = new LinkedList<Character>();
    int len = s.length();
    for(int count=0;count<len;count++)
        poss.add(s.charAt(count));
    generateRecurse(poss, len, "");
}
private static void generateRecurse(Queue<Character> possibles, int n, String word) {
    if(n==0)
        System.out.println(word);
    else {
        for(int count=0;count<n;count++) {
            char first = possibles.remove();
            generateRecurse(possibles, n-1, word+first);
            possibles.add(first);
        }
    }
}

我同意作者的观点，我的解决方案以 O(n!) 时间复杂度运行，因为要解决这个问题，你必须考虑阶乘，比如像“top”这样的词，第一个字母有 3 种可能，第一个字母有 2 种可能第二等等……

然而，她没有提到空间复杂性。我知道面试官喜欢问你解决方案的时间和空间复杂度。这个解的空间复杂度是多少？我最初的猜测是 O(n2)，因为在每个级别 n 有 n 个递归调用。所以你会加上 n + n - 1 + n - 2 + n - 3.....+ 1 得到 n(n+1)⁄2，它是 O(n2)。我推断有 n 个递归调用，因为您必须在每个级别回溯 n 次，并且空间复杂度是您的算法进行的递归调用的数量。例如，当考虑“TOP”的所有排列时，在级别，3次递归调用，gR([O,P],2,"T"), gR([P,T],2,"O"), gR([T,O],2,"P") 。我对空间复杂度的分析是否正确？

最佳答案

我认为你得到了正确的答案，但原因是错误的。递归调用的次数与它没有任何关系。当你进行递归调用时，它会给栈增加一定的空间；但是当该调用退出时，堆栈空间被释放。所以假设你有这样的事情:

void method(int n) {
    if (n == 1) {
        for (int i = 0; i < 10000; i++) {
            method(0);
        }
    }
}

method(1);

虽然 method调用自身 10000 次，仍然不会有超过 2 次 method 的调用在任何时候在堆栈上。所以空间复杂度是 O(1) [常数]。

您的算法具有空间复杂度 O(n2) 的原因是因为 word字符串。当n降到0，就会有len调用 generateRecurse 占用的堆栈条目.会有len最多堆栈条目，因此堆栈的空间使用量仅为 O(n)；但是每个堆栈条目都有自己的 word ，它们将同时存在于堆中；以及那些 word 的长度参数为 1, 2, ..., len ，当然加起来就是 (len * (len+1)) / 2 ，这意味着空间使用量为 O(n2)。

关于堆栈帧的更多信息:似乎对堆栈帧基础知识的解释会有所帮助...

“堆栈帧”只是作为“堆栈”一部分的内存区域。通常，堆栈是预定义的内存区域；然而，堆栈帧的位置和大小不是预定义的。当程序第一次执行时，堆栈上不会有任何东西(实际上，那里可能会有一些初始数据，但我们假设什么都没有，只是为了简单起见)。所以内存的栈区是这样的:
bottom of stack                                       top of stack
------------------------------------------------------------------
|                      nothing                                   |
------------------------------------------------------------------
^
+--- stack pointer

(这假设堆栈向上增长，从低地址到高地址。许多机器都有向下增长的堆栈。为简化起见，我将继续假设这是一台堆栈向上增长的机器。)

当一个方法(函数、过程、子程序等)被调用时，栈的某个区域被分配。该区域足以容纳方法的局部变量(或对它们的引用)、参数(或对它们的引用)、一些数据，以便程序在您return 时知道返回到哪里。 ，可能还有其他信息——其他信息高度依赖于机器、编程语言和编译器。在 Java 中，第一种方法是 main
bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame |                  nothing                        |
------------------------------------------------------------------
                ^
                +--- stack pointer

请注意，堆栈指针已向上移动。现在 main电话method1 .自 method1将返回 main ，main的局部变量和参数必须保留到何时 main可以继续执行。在堆栈上分配了一个具有某种大小的新帧:
bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame | method1's frame |      nothing                  |
------------------------------------------------------------------
                                  ^
                                  +--- stack pointer

然后 method1电话method2 :
bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame | method1's frame | method2's frame |   nothing   |
------------------------------------------------------------------
                                                    ^
                                                    +--- stack pointer

现在 method2返回。后 method2返回，其参数和局部变量将不再可访问。因此，可以抛出整个框架。这是通过将堆栈指针移回之前的位置来完成的。 (“前一个堆栈指针”是保存在某个帧中的东西之一。)堆栈返回如下所示:
bottom of stack                                       top of stack
------------------------------------------------------------------
| main's frame | method1's frame |        nothing                |
------------------------------------------------------------------
                                  ^
                                  +--- stack pointer

这意味着，此时，机器会将以堆栈指针开头的堆栈部分视为“未使用”。说 method2 不太正确的框架被重用。你不能真正使用已经不复存在的东西，而且 method2的框架不再存在。从概念上讲，堆栈中只有一个很大的空白区域。如 method1调用另一个方法，无论是 method2 , method1递归，System.out.println或其他东西，将在堆栈指针现在指向的位置创建一个新框架。此框架的大小可以小于、等于或大于 method2框架曾经是。它将占用 method2 所在的部分或全部内存。框架是。如果是另一个电话 method2 ，无论是使用相同还是不同的参数调用它都没有关系。没关系，因为程序不记得上次使用了什么参数。它只知道从堆栈指针开始的内存区域是空的并且可供使用。该程序不知道最近住在那里的框架是什么。那帧不见了，不见了，不见了。

如果你能遵循这个，你可以看到，在计算空间复杂度时，当只查看堆栈使用的空间量时，唯一重要的是，在任何一个时间点堆栈上可以存在多少帧?过去可能存在但不再存在的帧与计算无关，无论调用方法的参数是什么。

(P.S. 如果有人打算指出我在这个或那个细节上的技术错误——我已经知道这是一个严重的过度简化。)

关于java - 我对空间复杂度的分析是否正确？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29224822/

java我对codemethod的algorithmrecursiontime-complexityspace-complexity

有关java - 我对空间复杂度的分析是否正确？的更多相关文章

  1. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  2. ruby-on-rails - 如何使用 instance_variable_set 正确设置实例变量？ - 2

    我正在查看instance_variable_set的文档并看到给出的示例代码是这样做的:obj.instance_variable_set(:@instnc_var,"valuefortheinstancevariable")然后允许您在类的任何实例方法中以@instnc_var的形式访问该变量。我想知道为什么在@instnc_var之前需要一个冒号:。冒号有什么作用？ 最佳答案 我的第一直觉是告诉你不要使用instance_variable_set除非你真的知道你用它做什么。它本质上是一种元编程工具或绕过实例变量可见性的黑客攻击

  3. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  4. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  5. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  6. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  7. ruby - 检查日期是否在过去 7 天内 - 2

    我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/

  8. ruby - 如何验证 IO.copy_stream 是否成功 - 2

    这里有一个很好的答案解释了如何在Ruby中下载文件而不将其加载到内存中:https://stackoverflow.com/a/29743394/4852737require'open-uri'download=open('http://example.com/image.png')IO.copy_stream(download,'~/image.png')我如何验证下载文件的IO.copy_stream调用是否真的成功——这意味着下载的文件与我打算下载的文件完全相同，而不是下载一半的损坏文件？documentation说IO.copy_stream返回它复制的字节数，但是当我还没有下

  9. ruby - 是否可以覆盖 gemfile 进行本地开发？ - 2

    我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI

  10. ruby-on-rails - 正确的 Rails 2.1 做事方式 - 2

    question的一些答案关于redirect_to让我想到了其他一些问题。基本上，我正在使用Rails2.1编写博客应用程序。我一直在尝试自己完成大部分工作(因为我对Rails有所了解)，但在需要时会引用Internet上的教程和引用资料。我设法让一个简单的博客正常运行，然后我尝试添加评论。靠我自己，我设法让它进入了可以从script/console添加评论的阶段，但我无法让表单正常工作。我遵循的其中一个教程建议在帖子Controller中创建一个“评论”操作，以添加评论。我的问题是:这是“标准”方式吗？我的另一个问题的答案之一似乎暗示应该有一个CommentsController参

随机推荐