数据结构：常见时间复杂度与空间复杂度

时间复杂度与空间复杂度

一、复杂度的概念

• 一个算法的好坏，主要是对比两者的时间和空间两个维度，也就是时间和空间复杂度。
• 时间复杂度主要衡量一个算法运行的快慢，空间复杂度主要衡量一个算法运行需要的额外空间。

二、时间复杂度

• 算法的时间复杂度是一个函数式 T(N)，表示算法中的基本操作的执行次数，为算法的时间复杂度。
• 注：编译器的不同，编译所需要的时间也不同。越新的编译器，编译的时间往往比旧的编译器快。
• 当一个算法函数式为 T(N) = N，和另一个算法函数式为 T(N) = N^2 比较，必然是第一个快。

1. 大 O 的渐进表示法

大 O 渐进表示法的规则：

1. 时间复杂度函数式 T(N) 中，只保留最高阶项，去掉那些低阶项（当 N 无穷大时，低阶项的影响越来越小）。
2. 如果最高阶项是一个一次线性函数，则去除常数系数（当 N 无穷大时，1 的影响很小）。
3. T(N) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。

我们来判断一段代码的时间复杂度：

// 请计算一下 Func1 中++count 语句总共执行了多少次？
void Func1(int N) {
    int count = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            ++count;
        }
    }
    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }
    int M = 10;
    while (M--) {
        ++count;
    }
}

Func1 执行的基本操作次数：T(N) = N^2 + 2*N + 10 通过对 N 取值分析，对结果影响最大的一项是 N^2 通过以上方法，可以大致评估 Func1 的时间复杂度为：O(N^2)

2. 函数 clock 计算运算时间

我们想计算代码运算的时间，可以运用 clock 函数进行计算。运算过程为运算末 - 运算初。

#include <stdio.h>
#include <time.h>

  {
     i = ;
     n = ;
     begin = clock();
     x = ;
     (i = ; i < n; i++) {
        x++;
    }
     end = clock();
    
    (, end - begin);
     ;
}