算法复杂度分为 算法的时间复杂度  与  算法的空间复杂度；（本文重点介绍算法的时间复杂度）

1  概念

　　算法的时间复杂度：算法运行后对时间需求量的定性描述；

　　算法的空间复杂度：算法运行后对空间需求量的定性描述；

　　注：算法时间复杂度的使用方法  适用于 算法的空间复杂度；

2  大O表示法

　　由事前分析估算法可知，在判断算法效率时，可以将算法效率表达式中的常数项、其它次要项均舍弃，只保留算法效率表达式中的最高次项。基于这种思想，能不能有一种可以用符号定性的判断算法效率的方法呢？— 大O表示法就这么诞生了。

　　算法效率   主要是由   操作（Opetation）数量决定的；

　　操作数量的估算  可以用于  算法时间复杂度的估算；

　　在使用大O表示法进行算法的时间复杂度估算时，重点关注 操作数量的最高次项；

　　比如：O(5)= 0(1)  —  O(5)：表示算法运行至结束的操作数量为5  == 一般来说：定性分析常数项的操作数量就是0(1) 

　　　　   O(2n+ 1)= O(2n)= O(n)

　　　　   O(n2+ n + 1)= O(n2)

　　          O(3n3+1)= O(3n3)= O(n3)

3 常用的时间复杂度（线性阶、对数阶、平方阶）

　　1）线性阶时间复杂度 O(n)

for(int i=0; i<n; i++)
{
     // 复杂度为O(1) 的程序语句
}
// 循环次数: n

　　2）对数阶时间复杂度 O(logn)

int i = 1;
while( i < n)
{
     //复杂度为O(1)的程序语句
     i *= 2;
}　　
// 循环次数:log2n

　　3）平方阶时间复杂度 O(n2)

for(int i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
    {
        //复杂度为O(1)的程序语句
    }
}
// 循环次数: n^2

　　练习：

 1 for(int i = 0; i < n; i++)
 2 {
 3      for(j = i; j <n; j++)
 4      {
 5           //复杂度为O(1)的程序语句
 6      }
 7 }
 8 /*
 9     i = 0;   O(n)
10     i = 1;   O(n-1)
11     i = 2;   O(n-2)
12     ...
13     i = n-1;   O(1)
14     故：时间复杂度 = O( n + n-1 + n-2 ... + 1) = O( n(n+1)/2 ) = O(n^2)
15 */
 1 void f(int n)
 2 {
 3     int i = 0;
 4 
 5     while(i < n)
 6     {
 7         cout << i << endl;
 8     }
 9 }
10 
11 void func(int n)    // n(n+1) => 时间复杂度 = O( n(n+1) ) = O(n^2)
12 {
13     int i = 0;
14 
15     while( i < n)   // n
16     {
17         f(n);   // n
18         i++     // 1
19     }
 1 void f(int n)
 2 {
 3     int i = 0;
 4 
 5     while(i < n)
 6     {
 7         cout << i << endl;
 8     }
 9 }
10 
11 void func(int n)    // 时间复杂度 = O( n^3 + n^2 + n) = O(n^3)
12 {
13     f(n);   // O(n)
14 
15     for(int i = 0; i < n; i++)  // O(n^2)
16     {
17         f(n);
18     }
19 
20     for(int i = 0; i < n; i++)  // O(n^3) <= 两层for循环 O(n^2) * 函数 f(n) 的时间复杂度 O(n)
21     {
22         for(int j = i; j < n; j++)
23         {
24             f(n);
25         }
26     }
27 }

 

版权声明：本文为nbk-zyc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/nbk-zyc/p/12293186.html