通常规则是，如果存在 1 到 n 个元素的循环，则复杂度为 O(n)，进一步的嵌套循环为 nx O(n)。但是，我们什么时候说子程序的复杂度为 O(log n)？
问问题
278 次
2 回答
1
您可以将二进制搜索作为第一个示例。可以从一个相关的问题如何计算二分搜索复杂度来解释该算法的复杂性。表明这种复杂度的计算可以从递推式中得到。
于 2013-05-27T20:35:17.783 回答
1
当在每次迭代中我们将问题大小减小为 X 的一个因素时，我们可以说问题是O(log n)
例如 - 二分搜索：在每次迭代中，我们将问题大小减少 2 倍
于 2013-05-27T20:51:43.370 回答