草庐IT

java - 两个相关 for 循环的复杂度，外循环的复杂度为 log n

coder 2023-09-02 原文

问题

计算该算法的复杂度:

 for(i=n; i>1;i=i/2)
   for(j=i;j<n;j++){
         statement;
   }

我之前在这个话题上做过什么:

第一个循环运行 logn 次。 第二个循环运行 n-i 次，i 从 n 开始，并在每次外循环迭代中变为 i/2。所以内循环是这样运行的:

n-n                             0 times

n - n/2                        n/2 times

n - n/4                        3n/4 times

n - n/8                        7n/8 times

n - n/16                     15n/16 times

以此类推直到

n - 1 次

所以一般术语是n * ((2^n)-1)/(2^n)

现在这个数列既不是算术数列也不是几何数列。所以 n/2 * (a+l) 的公式不能应用于它。我如何进一步处理这个解决方案，或者如果它是错误的，那么正确的方法是什么。

注意:如果应用n/2*(a+l)，则生成的复杂度为-n/(2^n) = O(2^n)。

最佳答案

您走在正确的轨道上。正如您提到的，内部循环将运行 log n 次。所以，它运行的总次数是:

    (n - n/2) + (n - n/4) + ... (log n) times
  = n*(log n) - (n/2 + n/4 + n/8 + ... up to 1)
  = n*(log n) - n*(1/2 + 1/4 + ...)
 <= n*(log n) - n because (1/2 + 1/4 + ...) is 1 even if we take all terms till infinity (G.P)
  = n(log n - 1), which is O(n*log(n))

请记住，在计算复杂度时，您总是在寻找上限，而不是确切的数字。

关于java - 两个相关 for 循环的复杂度，外循环的复杂度为 log n，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18932387/

javaforcodesectionstrongalgorithmcomplexity-theory

有关java - 两个相关 for 循环的复杂度，外循环的复杂度为 log 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 - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  4. 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，如果没有检查，请帮助我，非常感谢,谢谢

  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 - 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

  8. ruby-on-rails - 相关表上的范围为 "WHERE ... LIKE" - 2

    我正在尝试从Postgresql表(table1)中获取数据，该表由另一个相关表(property)的字段(table2)过滤。在纯SQL中，我会这样编写查询:SELECT*FROMtable1JOINtable2USING(table2_id)WHEREtable2.propertyLIKE'query%'这工作正常:scope:my_scope,->(query){includes(:table2).where("table2.property":query)}但我真正需要的是使用LIKE运算符进行过滤，而不是严格相等。然而，这是行不通的:scope:my_scope,->(que

  9. 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背后的逻辑是什么？为什么不只有一个？

  10. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

随机推荐