时间复杂度

た入场券 2022-08-28 13:55 182阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 10]

1.我们知道常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；  
如果 T(n) 不等于一个常数项时，直接将常数项省略。

比如
    第一个 Hello, World 的例子中 T(n) = 2，所以我们说那个函数(算法)的时间复杂度为 O(1)。
    T(n) = n + 29，此时时间复杂度为 O(n)。

2.我们知道高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的。 同时因为要求的精度不高，所以我们直接忽略低此项。

比如
    T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)。

3.因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。

比如
    T(n) = 3n^3，此时时间复杂度为 O(n^3)。

综合起来：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。为了方便描述，下文称此为 大O推导法。  
   
由此可见，由执行次数 T(n) 得到时间复杂度并不困难，很多时候困难的是从算法通过分析和数学运算得到 T(n)。对此，提供下列四个便利的法则，这些法则都是可以简单推导出来的，总结出来以便提高效率。

**对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个  
循环的时间复杂度为 O(n×m)。**

void aFunc(int n) { 
        for(int i = 0; i < n; i++) {          // 循环次数为 n
            printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
        }
    }

此时时间复杂度为 O(n × 1)，即 O(n)。

**对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。**

void aFunc(int n) { 
        for(int i = 0; i < n; i++) {          // 循环次数为 n
            for(int j = 0; j < n; j++) {        // 循环次数为 n
                printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
            }
        }
    }

此时时间复杂度为 O(n × n × 1)，即 O(n^2)。

**对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。**

void aFunc(int n) { 
        // 第一部分时间复杂度为 O(n^2)
        for(int i = 0; i < n; i++) { 
            for(int j = 0; j < n; j++) { 
                printf("Hello, World!\n");
            }
        }
        // 第二部分时间复杂度为 O(n)
        for(int j = 0; j < n; j++) { 
            printf("Hello, World!\n");
        }
    }

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

**对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。**

void aFunc(int n) { 
        if (n >= 0) { 
            // 第一条路径时间复杂度为 O(n^2)
            for(int i = 0; i < n; i++) { 
                for(int j = 0; j < n; j++) { 
                    printf("输入数据大于等于零\n");
                }
            }
        } else { 
            // 第二条路径时间复杂度为 O(n)
            for(int j = 0; j < n; j++) { 
                printf("输入数据小于零\n");
            }
        }
    }

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

**时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/faa98c3bd8c54470b753ac0992327ae8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0e1b4cf449c24b7ca2c11cd724b2c077.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/477da4dd2a06431b9c706c877817d8c8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/8943679e673e4895b6ac5e88183e7a72.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/cd8890e1eadd439caebe2e40d549c89b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/0a9be043125e4d7995f55520bc927560.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/50e682b5e77644c68597913f13317bb5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/a0cd1165b137472fb0623539d11b8f6d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/a367f5ab5d954dd899af8524e92efd0f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/ca1c358815e641bb9c92aeb31445db8a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/345627ad1d6b44f583d6ef0490ca5412.png