我正在尝试学习如何找到各种算法的大θ界限，但我很难理解如何做到这一点，即使在阅读了这里的一些问题以及关于该主题的讲座和教科书之后也是如此。所以例如
procedure for array a{
step=1
while(step <= n){
i = n
while(i >= step){
a[i]= a[i-step] + a[i]
i = i - 1}
step = step * 2}
}
我想根据 n（数组 a 中的索引数）计算出加法数的大θ界限。我可以看到外循环本身经历了 log(n) 迭代，但我不知道如何表达内循环中发生的事情。有没有人有解释，甚至可能有我可以尝试咨询的资源？
Big Theta表示法要求我们找到 2 个常数，k1 和 k2，使得我们的函数 f(n) 在 k1*g(n) 和 k2*g(n) 之间对于足够大的 n。换句话说，我们能否找到一些其他函数 g(n) 在某个点小于 f(n) 而在另一个点大于 f(n)（单调每个方向）。
为了证明 Big-Theta，我们需要找到 g(n) 使得 f(n) 为 O(g(n))（上限），并且 f(n) 为 Big-Omega(g(n))（下限）边界）。
就Big-O表示法（其中 f(n) <= g(n)*k）而言，您的算法 f(n) 为 O(log(n)*n)，在这种情况下 g(n) =日志（n）* n。
让我们证明这一点：
外循环执行多少次？跟踪“step”变量：假设 n 为 100：
对于输入 100，这是 7 次执行。我们可以等效地说它执行(log n)次数（实际上是 floor(log n) 次，但 log(n) 就足够了）。
现在让我们看看内部循环。跟踪 i 变量，该变量从开始n并递减，直到step 每次迭代都具有大小。因此，对于 step 的每个值，内部 while 循环将执行 n - step 次。
例如，当n = 100
那么我们内部循环的总迭代次数是多少？
这东西怎么长的？好吧，因为我们知道外循环会迭代 log(n) 次，所以我们可以将这个东西表述为求和：
Sum(从 i=0 到 log(n)) n-2^i
= log(n)*n - Sum(从 i=0 到 log(n)) 2^i
= log(n)*n - (2^0 + 2^1 + 2^2 + ... + 2^log(n))
= log(n)*n - ( (1-2^log(n) ) / (1-2) ) （实际上是 2^log(n+1) 但足够接近）
= log(n)*n + 1 - n
所以现在我们的目标是证明：
日志(n)*n + 1 - n = O(log(n)*n)
显然，log(n)*n 是 O(log(n)*n)，但是1-n呢？
1-n = O(log(n)*n)？
1-n <= k*log(n)*n，对于一些 k？
让 k = 1
1-n <= log(n)*n?
两边加n
1 <= n*log(n) + n? 是的
所以我们已经证明 f(n) 是 O(n*log(n))。
现在我们使用 log(n) * n 获得了 f(n) 的上限，让我们尝试使用 log(n) * n 获得 f(n) 的下限。
对于下限，我们使用Big Omega表示法。Big Omega 为某个正常数 k 寻找函数 g(n)*k <= f(n)。
k(n*log(n)) <= n*log(n) + 1 - n?
让 k = 1/10
n*log(n)/10 <= n*log(n) + 1 - n?
(n*log(n) - 10n*log(n)) / 10 <= 1 - n?
-9n*log(n)/10 <= 1 - n? 乘以 10
-9n*log(n) <= 10 - 10n？乘以 -1（翻转不等式）
9n*log(n) >= 10n - 10？除以 9
n*log(n) >= 10n/9 - 10/9？除以 n
对数(n) >= 10/9 - 10/9n ? 是的
显然，随着 (10/9 - 10/9n) 趋向于 10/9，log(n) 的数量会变大。事实上，对于 n = 1，0 >= 10/9 - 10/9。0 >= 0。
所以现在我们已经证明了f(n) is Big-Omega(n*log(n))。将其与 的证明结合起来f(n) is O(n*log(n))，我们已经证明了这一点f(n) is Big-Theta(n*log(n))！（感叹号是为了兴奋，而不是阶乘……）
g(n) = n*log(n)，一组有效的常数是k1=1/10（下限）和k2 = 1（上限）。
简化代码的表示，如下所示，我们可以将您的代码转换为 Sigma 符号
for (step = 1; <= n; step = step * 2) {
for(i = n; i >= step; step = step - 1) {
}
}
像这样：
为了证明 big-O：外循环有floor(log2(n)) + 1 = O(log(n))迭代，内循环O(n)每次迭代，总共O(n * log(n)).
为了证明大欧米茄：floor(log2(n/2)) + 1 = Omega(log(n))通过外部循环进行迭代，在此期间step <= n/2. 内部循环的迭代n + 1 - step次数，对于这些外部迭代来说，超过n/2 = Omega(n)per，总共Omega(n * log(n)).
big-O 和 big-Omega 一起证明了 big-Theta。