<分区>
我在 Stack Overflow 上看到同一个问题 3 次: Complexity of an algorithm Time complexity for two pieces of code Tricky Big-O complexity
我想在其中一个问题中提出问题，但我不能，因为我是该网站的新手，无法发表评论。
有人可以向我解释为什么复杂度是 O(logm + logn) 而不是 O(logm * logn) 吗？ 我尝试自己解决它并且 O(logm * logn) 对我来说更有意义......因为例如如果你用 n=16 和 m=1000 运行它那么你会得到大约 6 + 4......而且它更有意义它会运行 6 * 4 次 ...
你能帮我解释一下吗..？谢谢:)
最佳答案
好吧，while 循环在 O(logm) 中运行，其中 log 的基数为 3，在 while 循环之后，外部 for 循环运行常数次 <= 100，内部 for 循环运行在O(logn)，其中对数的底数为 2。
因为它在 O(1) 中运行，所以可以忽略外部 for 循环(复杂性意味着忽略常量并研究增长，而不是算法执行的步骤数!)；该算法具有 O(logm + logn) 复杂度，因为首先你在 O(logm) 中有 while，然后在 O(logn) 中有 for(你在 while 中没有 for 来乘以它们)。
关于java - 为什么 O(logm + logn) 而不是 O(logm * logn)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23168135/