algorithm - 如果循环变量除/乘以恒定量，为什么我们将时间复杂度视为 O(Logn)？

Question

如果循环变量除/乘一个常数，为什么我们将时间复杂度视为 O(Logn)？ 就像，

 for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

Answer 1

好吧，这样想 - 如果常数是正整数，那么复杂度会比 2 更好。 。因此，通过考虑常数 2我们不会因暗示算法的复杂性(Big-Oh)而遭受任何损失。现在，如果您考虑 2那么它将运行大约 log_2(n)次。由此开始，它就出现了。

无论常数是什么(正整数)，复杂度的上限都是 O(log_2(n))因此，我们可以认为复杂度为 Big_O，其边界为 O(long_2(n)) 。准确的计算会给出O(log_C(n))其中O(log_C(n)) < O(log_2(n)) 。这就是为什么这个成立。