jjzjj

java - 这个函数(for 循环)空间复杂度是 O(1) 还是 O(n)？

coder 2024-03-18 原文 

public void check_10() {
    for (string i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}

这是 O(1) 还是 O(n)？我猜是 O(n)，但不是每次都重用内存 a 的位置使其成为 O(1) 吗？

最佳答案

空间复杂度询问“我在这段代码中使用了多少额外的空间(渐近地，说)”。以下是空间复杂度分析的工作方式，显示了两种一般情况(对于您的代码片段):
示例 1:按值传递 hashtable和 list

// assume `list` and `hashtable` are passed by value
public void check_10(List<String> list, HashMap<String, Integer> hashtable) {
    for (String i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}
假设你有 N hashtable 中的元素并且没有删除任何元素(即，所有 a <= 10 元素的 N)，在循环结束时，您将拥有 N hashtable 中剩余的元素.此外，每个String在 N hashtable 中的键最多包含 S人物。最后，每个Integer在 N hashtable 中的值是恒定的。
同样，您有一个可能的 M list 中的字符串数, 其中每个 String最多可包含 S人物。
最后，Integer a对分析没有贡献，因为它引用了已经考虑的内存。我们可以考虑这个Integer a内存犹新。
因此，假设 hashtable和 list已在方法中声明，您正在查看 O(N*S + M*S + I) 的空间复杂度.
也就是说，渐近地，我们并不真正关心 I ( Integer a )因为它是恒定大小，可能比 N 小得多和 M .同样，S可能比两者都小得多 N和 M .这意味着空间复杂度为 O(N + M) .因为两者都是线性项，我们可以(小心地)将其简化为 O(n) ，其中 n是一个线性项，它是 N and M 的线性组合.
示例 2:通过引用传递 hashtable和 list或在其他地方声明(如您的示例)
// assume `list` and `hashtable` are passed by reference or
// declared elsewhere in the class as in
//
// public void check_10() {
public void check_10(List<String> list, HashMap<String, Integer> hashtable) {
    for (String i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}
在这种方法中，list和 hashtable已经在别处分配了，这意味着该方法的空间复杂度为O(1)因为我们只在 Integer a 中使用常量空间和 String i (尽管从技术上讲，它们是对先前分配的内存的引用——您可以将常量空间视为存储引用的结果)。

but isn't it reusing the spot of memory a each time making it O(1)?


这取决于“重用”内存中的位置是什么意思。理论上，空间复杂度分析并没有完全考虑这个意义上的语言的实现细节。这意味着如果你有一个循环
for (int i = 0; i < N; i++) {
    T myvar = new T();
}
你没有考虑 myvar 所发生的事情的影响每次循环迭代后。通过“正在发生的事情的影响”，我的意思是垃圾收集器是在每次迭代后回收内存，还是在堆上不断分配 N 个内存点？在 GC 的情况下，它将是 O(1)因为你正在重用内存。在“无限”分配情况下，它将是 O(N)因为你现在有 N分配的名额。同样，理论上，这通常不会在分析中考虑，任何 T myvar = new T()通常被认为是 O(1)，无论它是否位于循环中。
但是，一般而言，如果您指的是将内存中的相同位置重用于 list和 hashtable每次迭代，答案都更简单。考虑以下:
public void foo() {
    int list[] = {1, 2, 3, 4};
    for (int i = 0; i < list.length; i++) {
        System.out.println(list[i]);
    }
}
即使 list声明一次，我们只遍历 list并打印内容，foo()内存复杂度仍然是 O(n) 因为我们已经分配了 list ，在渐近情况下可能有多达 n元素。因此，无论它是在内存中重用相同的点还是不同的点，它们仍然有助于线性空间复杂度。
tl;博士
但是，在您的特定情况下， list和 hashtable已经在程序的其他地方分配了，这里就不介绍了，所以不会增加复杂性，Integer a和 String i只在内存中保持不变。因此，此方法将是 O(1) .

关于java - 这个函数(for 循环)空间复杂度是 O(1) 还是 O(n)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34487306/

javaforcodehashtablelistalgorithmdata-structuresbig-ospace-complexity

有关java - 这个函数(for 循环)空间复杂度是 O(1) 还是 O(n)？的更多相关文章

  1. ruby - 树顶语法无限循环 - 2

    我脑子里浮现出一些关于一种新编程语言的想法，所以我想我会尝试实现它。一位friend建议我尝试使用Treetop(Rubygem)来创建一个解析器。Treetop的文档很少，我以前从未做过这种事情。我的解析器表现得好像有一个无限循环，但没有堆栈跟踪；事实证明很难追踪到。有人可以指出入门级解析/AST指南的方向吗？我真的需要一些列出规则、常见用法等的东西来使用像Treetop这样的工具。我的语法分析器在GitHub上，以防有人希望帮助我改进它。class{initialize=lambda(name){receiver.name=name}greet=lambda{IO.puts("He

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby-on-rails - form_for 中不在模型中的自定义字段 - 2

    我想向我的Controller传递一个参数，它是一个简单的复选框，但我不知道如何在模型的form_for中引入它，这是我的观点:{:id=>'go_finance'}do|f|%>Transferirde:para:Entrada:"input",:placeholder=>"Quantofoiganho?"%>Saída:"output",:placeholder=>"Quantofoigasto?"%>Nota:我想做一个额外的复选框，但我该怎么做，模型中没有一个对象，而是一个要检查的对象，以便在Controller中创建一个ifelse，如果没有检查，请帮助我，非常感谢,谢谢

  4. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  5. 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/

  6. ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2

    我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("

  7. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  8. ruby-on-rails - Rails 中的 NoMethodError::MailersController#preview undefined method `activation_token=' for nil:NilClass - 2

    似乎无法为此找到有效的答案。我正在阅读Rails教程的第10章第10.1.2节，但似乎无法使邮件程序预览正常工作。我发现处理错误的所有答案都与教程的不同部分相关，我假设我犯的错误正盯着我的脸。我已经完成并将教程中的代码复制/粘贴到相关文件中，但到目前为止，我还看不出我输入的内容与教程中的内容有什么区别。到目前为止，建议是在函数定义中添加或删除参数user，但这并没有解决问题。触发错误的url是http://localhost:3000/rails/mailers/user_mailer/account_activation.http://localhost:3000/rails/mai

  9. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  10. ruby-on-rails - 如何重命名或移动 Rails 的 README_FOR_APP - 2

    当我在我的Rails应用程序根目录中运行rakedoc:app时，API文档是使用/doc/README_FOR_APP作为主页生成的。我想向该文件添加.rdoc扩展名，以便它在GitHub上正确呈现。更好的是，我想将它移动到应用程序根目录(/README.rdoc)。有没有办法通过修改包含的rake/rdoctask任务在我的Rakefile中执行此操作？是否有某个地方可以查找可以修改的主页文件的名称？还是我必须编写一个新的Rake任务？额外的问题:Rails应用程序的两个单独文件/README和/doc/README_FOR_APP背后的逻辑是什么？为什么不只有一个？

随机推荐