下面算法的时间复杂度为 O ( 1 ) O(1) O(1)
void fun()
{
int result = 100;
result++;
printf("%d\n", result);
}
下面算法的基本操作执行了 100 100 100 次，时间复杂度为 O ( 1 ) O(1) O(1)
void fun(int n)
{
int count = 0;
for (int k = 0; k < 100; k++)
{
++count;
}
printf("%d\n", count);
}
在下面算法中，循环体中的代码执行了 n n n 次，时间复杂度为 O ( n ) O(n) O(n)
void fun(int n)
{
for (int i = 0; i < n; i++)
{
printf("%d\n", i);
}
}
在下面算法中，result 每次乘以 2 2 2，会越来越接近 n n n，当 result 大于等于 n n n 时，就会退出循环。
假设循环次数为 k k k，则有 2 k = n 2^k=n 2k=n，于是 k = log 2 n k=\log_{2}{n} k=log2n，因此时间复杂度为 O ( log n ) O(\log{n}) O(logn)。
void fun(int n)
{
int result = 1;
while (result < n)
{
result = result * 2;
}
}
下面算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
void fun(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d\n", result[i][j]);
}
}
}
下面算法的时间复杂度为 O ( n ∗ m ) O(n*m) O(n∗m)
void fun()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
a[i][j] = 0;
}
}
}
下面算法的时间复杂度为 O ( n ∗ log n ) O(n*\log{n}) O(n∗logn)
void fun(int n)
{
int count = 0;
for (int k = 1; k <= n; k *= 2)
{
for (int j = 1; j <= n; j++)
{
count++;
}
}
}
在下面算法中，基本操作的执行次数为 n + ( n − 1 ) + . . . + 2 + 1 = n ( n + 1 ) 2 n+(n-1)+...+2+1 = \frac{n(n+1)}{2} n+(n−1)+...+2+1=2n(n+1)，时间复杂度为 O ( n 2 ) O(n^2) O(n2)
void fun(int n)
{
int x = 0;
for (int i = 0; i < n; i++)
{
for (int j = n; j >= i + 1; j--)
{
x++;
}
}
}
假设基本操作的执行次数为 k k k，则有 k 3 = n k^3 = n k3=n，即 k = n 3 k=\sqrt[3]{n} k=3n ，因此时间复杂度为 O ( n 3 ) O(\sqrt[3]{n}) O(3n )
void fun(int n)
{
int i = 0;
while (i * i * i <= n)
{
i++;
}
}
总的时间复杂度等于其中最大的时间复杂度，因此下面代码的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
void fun(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d\n", a[i][j]);
}
}
for (int i = 0; i < n; i++)
{
printf("%d\n", b[i]);
}
}
总的时间复杂度等于其中最大的时间复杂度，因此下面代码的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
if (flag)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; i++)
{
printf("%d\n", a[i][j]);
}
}
}
else
{
for (int i = 0; i < n; i++)
{
printf("%d\n", b[i]);
}
}
递推方程
T ( n ) = a T ( n / b ) + f ( n ) T(n) = a T(n/b) + f(n) T(n)=aT(n/b)+f(n)
a a a：归约后的子问题个数
n / b n/b n/b：归约后子问题的规模
f ( n ) f(n) f(n)：归约过程及组合子问题的解的工作量
主定理（master theorem）
设 a ≥ 1 , b > 1 a \geq1, b>1 a≥1,b>1 为常数， f ( n ) f(n) f(n) 为函数， T ( n ) T(n) T(n) 为非负整数，且 T ( n ) = a T ( n / b ) + f ( n ) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n)，则
若 f ( n ) = O ( n log b a − ξ ) ， ξ > 0 f(n)=O(n^{\log_ba-\xi})，\xi>0 f(n)=O(nlogba−ξ)，ξ>0，那么 T ( n ) = Θ ( n log b a ) T(n)=\Theta(n^{\log_ba}) T(n)=Θ(nlogba)
若 f ( n ) = Θ ( n log b a ) f(n)=\Theta(n^{\log_ba}) f(n)=Θ(nlogba)，那么 T ( n ) = Θ ( n log b a log n ) T(n)=\Theta(n^{\log_ba} \log n) T(n)=Θ(nlogbalogn)
若 f ( n ) = Ω ( n log b a + ξ ) ， ξ > 0 f(n)=\Omega(n^{\log_ba + \xi})，\xi > 0 f(n)=Ω(nlogba+ξ)，ξ>0，且对于某个常数 c < 1 c<1 c<1 和充分大的 n n n 有 a f ( n / b ) ≤ c f ( n ) af(n/b) \leq cf(n) af(n/b)≤cf(n)，那么 T ( n ) = Θ ( f ( n ) ) T(n)=\Theta(f(n)) T(n)=Θ(f(n))
主定理（简化快速记忆）
对于 T ( n ) = a T ( n / b ) + f ( n ) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n)：
若 f ( n ) < n log b a f(n) < n^{\log_ba} f(n)<nlogba，则 T ( n ) = Θ ( n log b a ) T(n)=\Theta(n^{\log_ba}) T(n)=Θ(nlogba)
若 f ( n ) = n log b a f(n)=n^{\log_ba} f(n)=nlogba，则 T ( n ) = Θ ( n log b a log n ) T(n)=\Theta(n^{\log_ba} \log n) T(n)=Θ(nlogbalogn)
若 f ( n ) > n log b a f(n) > n^{\log_ba} f(n)>nlogba，则 T ( n ) = Θ ( f ( n ) ) T(n)=\Theta(f(n)) T(n)=Θ(f(n))
常见的递推式与复杂度
