时间复杂度

导：函数的渐进增长

判断一个算法的效率时候，函数中的常数和其他次要项常常可以忽略，更应该关注主项（最高项）的阶数。

定义

  • 在进行算法分析时，语句总的执行次数T(n)是关于规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。
  • 算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。
    它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，橙汁算法的渐进时间复杂度，简称为时间复杂度。
  • 其中f(n)是问题规模n的某个函数

注：

  • 一般情况下，随着规模n的增大，T(n)增长最慢的算法为最优算法
  • 显然，由算法时间复杂度定义可知，三个求和算法的时间复杂度分别为O(1)，O(n)，O(n2）。

推导时间复杂度的方法

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行函数中，只保留最高阶项
  3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数
  4. 得到结果即为时间复杂度

时间复杂度情况

常数阶

程序片段如下：

1
2
3
4
5
6
7
int sum=0;n=100;    cout<<"Hello world";
cout<<"Hello world";
cout<<"Hello world";
cout<<"Hello world";
cout<<"Hello world";
cout<<"Hello world";
sum=(n+1)*n/2;

时间复杂度为O(8)

而是O(1) √（常数级统一用1表示）

线性阶

一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模n的增大，对应计算次数呈直线增长。

1
2
3
4
5
int i,n=100,sum=0;
for(i=0;i<n;i++)
{
    sum+=i;
}

时间复杂度：O(n)；

因为循环体中的代码需要执行n次。

平方阶

嵌套循环涉及平方阶

1
2
3
4
5
6
7
8
int i=,i,n=100;
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        cout<<"Hello,world!";
    }
}

时间复杂度：O(n2)

升级版↓

1
2
3
4
5
6
7
8
int i=,i,n=100;
for(i=0;i<n;i++)
{
    for(j=i;j<n;j++)
    {
        cout<<"Hello,world!";
    }
}

分析

需要执行n+(n-1)+(n-2)+···+1次

即为$\frac{(n+1)*n}{2}$次，即为n2/2+n/2

去除低阶加法项，去除最高阶系数

时间复杂度为O(n2)

对数阶

程序片段如下↓

1
2
3
4
5
int i=1,n=100;
while(i<n)
{
    i=i*2;
}

分析

假设程序需要执行m次

2m=n

m=$\log_2 n$

时间复杂度为O($\log_2 n$)

函数调用的时间复杂度分析

程序片段↓

1
2
3
4
5
6
7
8
9
10
int i,j,n=100;
for(i=0;i<n;i++)
{
    fun(i);
}
void fun(int num)
{
    cout<<num;
    cout<<num;
}

分析

fun函数的时间复杂度为O(1)

程序在循环中调用n次fun函数

程序的时间复杂度为O(n)

升级版↓

如果fun函数的时间复杂度为O(n)

1
2
3
4
5
6
7
8
void fun(int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        cout<<i;
    }
}

那么程序的for循环调用n次fun函数

时间复杂度为O($n^2$)

再升级版↓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int i,n=100;
i++;
fun(n);
for(i=0;i<n;i++)
{
    fun(i);
}
for(i=0;i<n;i++)
{
    for(j=i;j<n;j++)
    {
        cout<<"Hello,world!"
    }
}
void fun(int num)
{
    cout<<num; 
}

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int i,n=100;
i++;  //时间复杂度：O(1)
fun(n);//时间复杂度：O(n)
for(i=0;i<n;i++)//循环时间复杂度：O(n^2)
{
    fun(i);
}
for(i=0;i<n;i++)//嵌套循环时间复杂度：O(n^2)
{
    for(j=i;j<n;j++)
    {
        cout<<"Hello,world!"
    }
}
void fun(int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        cout<<i;
    }
}

因为并列，所以三个时间复杂度相加=2*$n^2$+n+1

整个程序时间复杂度为O($n^2$)

总结

例子 时间复杂度 类型
5201314 O(1) 常数阶
3n+4 O(n) 线性阶
3$n^2$+4n+5 O($n^2$) 平方阶
3$\log_2 n$+4 O($\log_2 n$) 对数阶
2n+3n$\log_2 n$+14 O(n$\log_2 n$) n$\log_2 n$阶
$n^3$+2$n^2$+4n+6 O($n^3$) 立方阶
$2^n$ O($2^n$) 指数阶
  • 常用的时间复杂度所耗费的时间从小到大依次是
    O(1)< O($\log_2 n$)< O(n)< O(n$\log_2 n$)< O($n^2$)< O($n^3$)< O($2^n$)< O(n!)< O($n^n$)

空间复杂度

  • 通过计算算法所需的存储空间实现
  • 计算公式记作：S(n)=O(f(n))
    　其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数
  • 通常，“时间复杂度”指运行时间的需求，“空间复杂度”指空间需求。