如何计算给定关系式的时间复杂度？及大O符号相关复杂度证明咨询

Hey there! Let's tackle your two questions step by step—no jargon overload, just clear, practical explanations.

计算时间复杂度的方法主要分两类：针对递归关系式的，和针对非递归代码/表达式的。 Here are the most commonly used approaches:

• 主定理（Master Theorem）：This is a "shortcut tool" for divide-and-conquer recursive relations, applicable to formulas like T(n) = a*T(n/b) + f(n) (where a≥1, b>1, and f(n) is an asymptotically positive function). It has three cases:

  • If f(n) = O(n^log_b a - ε) (ε>0), then T(n) = Θ(n^log_b a)
  • If f(n) = Θ(n^log_b a * log^k n) (k≥0), then T(n) = Θ(n^log_b a * log^{k+1} n)
  • If f(n) = Ω(n^log_b a + ε) (ε>0), and the regularity condition a*f(n/b) ≤ c*f(n) holds (c<1, for sufficiently large n), then T(n) = Θ(f(n))

• 递归树法：Unfold the recursion into a tree, calculate the total time for each layer, then sum up all layers. For example, for the recursion T(n) = 2*T(n/2) + n, each layer of the tree has a total time of n, the tree height is log₂n, so the total time is n*log₂n, giving a complexity of O(n logn).

• 代入法（Substitution Method）：First guess a complexity result, then verify it with mathematical induction. For example, assume T(n) = O(n logn), substitute it into the recursive formula and check if you can find constants and n₀ that satisfy the definition of Big O.

• 迭代展开法：Unfold the recursive formula step by step until you get a general term. For example, T(n) = T(n-1) + n unfolds to T(1) + 1 + 2 + ... + n, which sums to n(n+1)/2 + T(1), so the asymptotic complexity is O(n²).

For non-recursive expressions or code, directly count the number of basic operations: a single loop is O(n), two nested loops are O(n²), a loop with a binary search (O(logn)) inside is O(n logn), etc.

The conclusion is: Yes, it holds. Let's prove it step by step:

First, recall the definition of Big O: since f(n) = O(g(n)), there exist constants k>0 and n₀>0 such that for all n≥n₀, f(n) ≤ k*g(n).

Next, handle the logarithmic part:
log₂(f(n)·c) = log₂f(n) + log₂c (by the product rule of logarithms). Here, log₂c is a fixed constant, so log₂(f(n)·c) = Θ(log₂f(n))—meaning it's asymptotically equivalent to log₂f(n).

Then, since f and g are non-decreasing and always greater than 1, for sufficiently large n, log₂f(n) ≤ log₂(k*g(n)) = log₂k + log₂g(n). As n grows, log₂g(n) will be much larger than the constant log₂k, so we can find a constant C>0 such that log₂f(n) ≤ C*log₂g(n) (for example, take C = log₂k + 1, which works when log₂g(n) ≥ 1, which is true for large enough n).

Now combine the two parts:
For n≥n₀:
f(n) * log₂(f(n)·c) ≤ k*g(n) * C*log₂g(n) = (k*C)*g(n)*log₂g(n)

Here, k*C is a fixed constant, which perfectly fits the definition of Big O—there exists a constant M=kC and n₀ such that the left-hand side is ≤ Mright-hand side for all n≥n₀. So f(n)∗log₂(f(n)·c)=O(g(n)∗log₂(g(n))) holds.

A quick example to verify: Let f(n)=n, g(n)=2n (clearly f(n)=O(g(n))), c=4. The left side is n*log₂(4n)=n*(2+log₂n), the right side is 2n*log₂(2n)=2n*(1+log₂n). The asymptotic complexity of the left is O(n logn), and the right is also O(n logn)—so the left is indeed within the Big O of the right.

内容的提问来源于stack exchange，提问作者ParthS007