本章重点

1. ​​什么是数据结构？

2. 什么是算法？

3. 算法效率

4. 时间复杂度

5. 空间复杂度

6. 常见时间复杂度以及复杂度oj练习

1. 什么是数据结构？

        数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

2.什么是算法？

        算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。比如：查找、排序等等。

3.算法效率

3.1 如何衡量一个算法的好坏

        我们能不能用一个程序运行的开始的时间到程序结束的时间去描述复杂度呢？

答案是不能，一个程序的运行还会受到很多因素的影响，比如电脑的配置、性能。就比如下面两台电脑，让两台电脑同时执行下面递归计算斐波那契数列40是多少的程序。很明显高性能的计算机器多核CPU，进程并发执行，速度高于左边的单核机器。

#include<stdio.h>
long long Fib(int N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
int main()
{//使用斐波那契数列递归方法计算40long long result = Fib(40);printf("%lld", result);return 0;
}

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

        算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

        时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

        在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

4.时间复杂度

        时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

        一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。

        一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

        即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

 Func1 执行的基本操作次数 ：

        我们发现当N的值越来越多的时候，2*N + 10这个表达式对结果造成的影响非常小，所有实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

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

使用大O的渐进表示法以后，Func1的时间复杂度为：

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况：

• 最坏情况：任意输入规模的最大运行次数(上界)
• 平均情况：任意输入规模的期望运行次数
• 最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

• 最好情况：1次找到
• 平均情况：N/2次找到
• 最坏情况：N次找到

        在实际中一般情况关注的是算法的最坏运行情况，原因是为了保证算法在任何输入情况下都能保持一定的性能水平。最坏情况时间复杂度是对算法性能的一个保证，确保在任何可能的输入下，算法都不会执行得更差。所以数组中搜索数据时间复杂度为.

常见时间复杂度计算举例

实例一：

// 计算Func2的时间复杂度？
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

1. 第一个循环：for (int k = 0; k < 2 * N; ++k)

   • 这个循环执行了 2 * N 次，其中 N 是输入的参数。
   • 循环内部只有一个基本操作 ++count。

2. 第二个循环：while (M--)

   • 这个循环执行了固定的 10 次。
   • 循环内部只有一个基本操作 ++count。

因此，总的基本操作数可以表示为：2 * N + 10。

        在大O符号表示法中，我们通常关注最高阶的项，而忽略低阶项和常数系数。在这种情况下，最高阶项是 2 * N。

        因此，Func2 函数的时间复杂度可以表示为 O(N)。

实例二：

//计算Func3的时间复杂度？
void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\n", count);
}

1. 第一个循环：for (int k = 0; k < M; ++k)

   • 这个循环执行了 M 次，其中 M 是第二个输入参数。
   • 循环内部只有一个基本操作 ++count。

2. 第二个循环：for (int k = 0; k < N; ++k)

   • 这个循环执行了 N 次，其中 N 是第一个输入参数。
   • 循环内部只有一个基本操作 ++count。

因此，总的基本操作数可以表示为：M + N。

        在大O符号表示法中，我们通常关注最高阶的项，而忽略低阶项和常数系数。在这种情况下，最高阶项是 M 和 N，同时取两者。

        因此，Func3 函数的时间复杂度可以表示为 O(M + N)。

补充：

• 若 M 和 N 的值相同，时间复杂度可以表示为 O(M) 或者 O(N)。
• 若 M >> N 的值，时间复杂度可以表示为 O(M)。
• 若 M << N 的值，时间复杂度可以表示为 O(N)。

在这种情况下，最高阶项是 M 或 N，取两者中较大的一个因此，Func3 函数的时间复杂度可以表示为 O(max(M, N))。

实例三：

// 计算Func4的时间复杂度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

1. 循环：for (int k = 0; k < 100; ++k)

   • 这个循环总共执行了 100 次。
   • 循环内部只有一个基本操作 ++count。

因此，总的基本操作数可以表示为：100。

        在大O符号表示法中，我们通常关注最高阶的项，而忽略低阶项和常数系数。在这种情况下，最高阶项是 100。

        因此，Func4 函数的时间复杂度可以表示为 O(1)。

实例四：

// 计算strchr的时间复杂度？
const char* strchr(const char* str, int character);

  strchr 函数用于在给定字符串中查找第一个出现的指定字符，并返回该字符后的部分字符串。

• 最好情况：1次找到
• 平均情况：N/2次找到
• 最坏情况：N次找到

        在一般情况下，strchr 函数的时间复杂度可以被认为是 O(N)，其中 N 是输入字符串的长度。这是因为 strchr 需要遍历字符串中的每个字符来查找指定字符。在最坏情况下，它可能需要遍历整个字符串才能找到目标字符。

 

实例五：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

        BubbleSort 是一种基本的排序算法，其时间复杂度取决于待排序数组的初始状态。让我们分析一下 BubbleSort 的时间复杂度。

        BubbleSort 的主要思想是在每一轮遍历中，比较相邻的两个元素，如果顺序不对就交换它们，直到最大（或最小）元素“冒泡”到正确的位置。在每一轮遍历中，至少会将一个元素放置在其最终的位置上。

        最坏情况下，数组完全逆序，需要执行 N-1 轮比较和交换操作。第一轮中，需要比较和可能的交换 N-1 次；第二轮中，需要比较和可能的交换 n-2次...

        所以，总的操作次数为：(N-1) * N / 2 = N * N / 2 - N / 2

在大O符号表示法中，我们通常关注最高阶的项，而忽略低阶项和常数系数。在这种情况下，最高阶项是 n^2。因此，BubbleSort 的时间复杂度可以表示为 O(n^2)。

        需要注意的是，BubbleSort 的平均和最坏情况下的时间复杂度都是 O(N^2)，即使在最好情况下，数组已经是有序的，BubbleSort 也需要进行 n-1 轮比较，时间复杂度都是 O(N)。

实例六：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;
}

        BinarySearch（二分查找）是一种高效的查找算法，它的时间复杂度为 O(log N)，其中 N 是待查找数组的长度。

        在每一轮循环中，BinarySearch 将当前搜索范围缩小为原来的一半。假设当前搜索范围的长度为 len，在下一轮循环中，搜索范围的长度将减半为 len/2。因此，每一轮循环都可以排除一半的元素。

        最坏情况下，当搜索范围缩小到只有一个元素时，算法结束。而要将 n 个元素缩小到 1 个元素，需要进行 log₂(n) 次操作。

        因此，BinarySearch 的时间复杂度是 O(log n)。

        BinarySearch 在已排序的数组中查找元素，通过不断缩小搜索范围，每次排除掉一半的元素，因此它的时间复杂度非常低。

图解：

 实例七：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

阶乘递归函数 Fac 的时间复杂度可以通过递归关系来分析。在这种情况下，递归的深度与输入规模 N 相关，每一层递归都会进行一次乘法操作。让我们分析一下：

1. 第一递归层（N = N）：执行 1 次 Fac(N - 1) * N乘法。
2. 第二递归层（N = N-1）：执行 1 次 Fac(N - 2) * N乘法。
3. 第三递归层（N = N-2）：执行 1 次 Fac(N - 1) * N乘法。
4. ...
5. 最后一层递归（N = 0）：执行 1 次 Fac(0) * N乘法。

        总的乘法操作次数为 N 次。

因此，阶乘递归函数 Fac 的时间复杂度可以表示为 O(N)，其中 N 是输入的规模。

        尽管递归函数的每一层都只执行了一个乘法操作，但由于递归的深度与输入规模相关，最终的时间复杂度是线性的。

        总结：递归算法时间复杂度是多次调用的累加。

扩展：

//计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{if (0 == N)return 1;for (size_t i = 0; i < N; ++i){++count;}return Fac(N - 1) * N;
}

阶乘递归函数 Fac 的时间复杂度可以通过递归关系来分析。在这种情况下，递归的深度与输入规模 N 相关，每一层递归都会进行一次乘法操作。让我们分析一下：

1. 第一递归层（N = N）：执行 1 次 Fac(N - 1) * N 乘法 + 执行 N 次 ++count。
2. 第二递归层（N = N-1）：执行 1 次 Fac(N - 2) * N 乘法 + 执行 N-1 次 ++count。
3. 第三递归层（N = N-2）：执行 1 次 Fac(N - 1) * N 乘法 + 执行 N-2 次 ++count。
4. ...
5. 最后一层递归（N = 0）：执行 1 次 Fac(0) * N 乘法 + 执行0次 ++count。

由于上面每次递归执行的乘法只有一次，对于总的操作次数影响较小，可以忽略不记，所以总的操作次数为 N * N /2 次。

因此，阶乘递归函数 Fac 的时间复杂度可以表示为 O(N^2)，其中 N 是输入的规模。

        尽管递归函数的每一层都只执行了一个乘法操作，但由于递归的深度与输入规模相关，最终的时间复杂度是线性的。

        总结：递归算法时间复杂度是多次调用的累加。

实例八：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

斐波那契递归函数 Fib 的时间复杂度可以通过递归关系来分析。在这种情况下，递归的深度与输入规模 N 相关，每一层递归都会进行两次递归调用。让我们分析一下：

1. 第一层递归（N = N）：执行 2^0 次递归调用。
2. 第二层递归（N = N-1）：执行 2^2 次递归调用。
3. 第三层递归（N = N-2）：执行 2^3 次递归调用。
4. ...

        每一层递归调用的次数是指数级别增长的， 总的乘法操作次数为 2^N-1 次。 

        因此，总的递归调用次数可以近似表示为 2^N 次。

        由于每次递归调用都需要一些操作（在这里是两次递归调用），在最坏情况下，每次递归调用的时间开销相对较小。因此，总的时间复杂度仍然可以表示为 O(2^N)。

但是实际上右边会缺少，总的时间复杂度低于等于 O(2^N)。

5.空间复杂度 

        空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外临时占用存储空间大小的量度 。

        空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

        空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

        注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

实例一：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

        在 BubbleSort 中，输入数组不是额外开辟的空间，不算入到空间复杂度上，其余只使用了很少的额外空间，主要是用来存储一些临时变量，如循环索引、交换标志等。这些额外空间的使用量不会随着输入规模 n 的增加而显著变化。无论输入数组的大小如何，BubbleSort 需要的额外空间是固定的。

        因此，BubbleSort 的空间复杂度为 O(1)。

实例二：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

1. 额外数组的空间： 在 Fibonacci 函数内部，通过动态内存分配 malloc 来创建一个大小为 (n + 1) 的长整型数组 fibArray，用于存储斐波那契数列的前 n 项。这个数组的空间占用是与 n 相关的。

        所以，总的空间复杂度由额外数组的空间复杂度决定。

        在这种情况下，空间复杂度是 O(N)。

实例三：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

        阶乘递归函数 Fac 的空间复杂度是 O(N)，因为每次递归调用都会在函数调用栈上创建一个新的递归帧，每个递归帧需要一些内存空间来存储局部变量、返回地址等。

        在最坏情况下，当递归深度达到 N 时，需要在栈上保留 N 层递归帧。因此，空间复杂度与递归的深度成正比，为 O(N)。

实例四：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

        这个斐波那契递归函数的空间复杂度是 O(N)。虽然函数本身没有显式地使用额外的数组或数据结构，但是在递归调用的过程中，每次调用都会在函数调用栈中创建一个新的函数调用帧。由于递归函数会多次调用自身，每次调用都需要分配一些内存来存储函数参数、局部变量以及返回地址等信息，这些内存会随着递归深度的增加而累积。递归深度直接影响了调用栈中需要分配的内存空间数量。

        我们拿 Fib(6) 举例，在这个递归实现中，当你调用 Fib(6) 时，它会依次调用 Fib(5) 和 Fib(4)，然而并不是右边那个Fib(4) ，是 Fib(5) 下面的 Fib(4) ，然后这些调用会进一步调用更低层次的函数，以此类推。当调完 Fib(2)后该函数栈帧就销毁了，然后生成 Fib(1)的栈帧， Fib(1)调完后也就释放了，以此类推。由于栈空间是可以复用的，一个栈帧释放空间就还给操作系统了，可以给后面的函数调用留下空闲的空间，整个过程中，递归最深的层数也就是Fib(6)到 Fib(2)了，其余调用的都是之前栈帧释放的空间，且深度也低。

        因此，递归的空间复杂度通常与递归的深度成正比，即 O(N)。这意味着在最坏情况下，调用栈的深度将达到 N 层，每一层都需要一些内存空间。这也是为什么递归在解决某些问题时可能会导致栈溢出或效率较低的原因之一。

下面这个例子就证明了栈空间是可复用滴。

#include<stdio.h>
void Func1()
{int a = 0;printf("%p\n", &a);
}
void Func2()
{int b = 0;printf("%p\n", &b);
}
int main()
{Func1();Func2();return 0;
}

运行结果：

        因为在许多编译器和操作系统中，函数调用时会使用相同的堆栈帧空间。这意味着在一个函数结束后，其分配给局部变量的堆栈空间可能会被重用给下一个函数的局部变量。

        因此，虽然在逻辑上 Func1 和 Func2 是在不同的函数调用中，它们的局部变量 a 和 b 分别被分配到了相同的堆栈空间（因为这两个函数的栈帧在调用时被重用），从而导致它们的局部变量的地址也相同。

结束啦！！！