时间复杂度与空间复杂度

数据结构与算法

---

概念

时间频度：一个算法的语句实际执行次数n（含系数），记作T(n)
时间复杂度：一个算法的语句受执行次数n的变化影响最大的一项（不含系数），记作O(n)

时间频度不同，但时间复杂度可能一致：

$$T(n) = n^2 + 3n + 4$$ 与 $$T(n) = 4n^2 + 2n + 1$$
时间复杂度不处理系数，所以以上两者均为 $$O(n^2)$$

例子

按数量级递增排列，常见的时间复杂度有：

类型	表达式
常数阶	$$O(1)$$
对数阶	$$O(log_2n)$$
线性阶	$$O(n)$$
线性对数阶	$$O(n log_2 n)$$
平方阶	$$O(n^2)$$
立方阶	$$O(n^3)$$

常数阶 $$T(n)=O(1)$$

以下三条语句的频度均为1，该程序段的执行时间与问题规模n无关。
故为常数阶，记作： T(n)=O(1)

Temp = i;
i = j;
j = temp;   

线性阶 $$O(n)$$

案例：循环了n - 1 ≈ n，就是O(n)

i = 1;
k = 0;
while(i <= n-1){
   k += 10 * i;
   i++;
}

平方阶 $$O(n^2)$$

案例一：循环了n*n次，记作：O(n^2)

for(i=1;i<=n;i++)   //循环了n*n次，当然是O(n^2)
    for(j=1;j<=n;j++)
        s++;

案例二：循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)

for(i=1;i<=n;i++) //循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)
    for(j=i;j<=n;j++)
        s++;

案例三：循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)

for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
         s++;

相关数学规律：n^2 恒大于 2n - 1

附

对数

定义：如果

$$N = a^x (a > 0,a <> 1)$$
即a的x次方等于N(a > 0且a <> 1)，那么数x叫做以a为底N的对数，记作
$$x = log_aN$$

常用公式
$$log_aa=1$$
$$log_a MN = log_aM + log_aN$$
$$log_a M/N = log_aM - log_aN$$
$$log_a M^N = nlog_aM$$
$$log_ab = log_cb/log_ca$$
$$log_ab * log_ba = 1$$
$$log_a^nM = log_aM / n$$