程序的最坏情况或平均情况如何与对数函数相关?对数的底数如何发挥作用?
当你将问题分成 k
个部分,每部分的大小为 n/k
,然后对其中一些部分进行“递归”(或模拟递归)时,就会出现对数因子。
一个简单的例子是以下循环:
foo(n):
while n > 0:
n = n/2
print n
n, n/2, n/4, .... , 1
这些值,总共有 O(logn)
个这样的值。
O(logn)
,因为每次打印都需要固定的时间,而沿途要经过的值的数量是 O(logn)
。n
的数组分成两个大小为 n/2
的子数组,然后对它们进行递归,并且在每个子数组上调用算法。T(n) = 2T(n/2) + O(n)
根据主定理,时间复杂度为 Theta(nlogn)
。
同样,在二分查找时,将问题分成两部分,仅对其中一个进行递归:
T(n) = T(n/2) + 1
这部分将会在 Theta(logn)
的时间复杂度内完成。
在大O复杂度中,底数不是一个因素,因为
log_k(n) = log_2(n)/log_2(k)
并且对于任意常数k
,log_2(k)是一个定值。
O(1)
还是O(logn)
? - nymkO(1)
。然而,从理论上讲 - 是的,对于任何大小和无界整数,它将是O(logN)
,因为一个整数N
需要O(logN)
位/数字来表示。 - amitprint n
不是O(logn)
,因为 n 会被反复除以2。 - nymklog(n) + log(n/2) + log(n/4) + ... + 1 = log(n) + (log(n)-1) + (log(n)-2) + ... + 1
这是等差数列,其和为O(log(n)^2)。 - amit