算法效率的钥匙：从大O看复杂度计算-海口c网

1.数据结构与算法

1.1数据结构介绍

1.2算法介绍

2.算法效率

2.1复杂度

2.1.1时间复杂度

2.1.1.1时间复杂度计算示例1

2.1.1.2时间复杂度计算示例2

2.1.1.3时间复杂度计算示例3

2.1.1.4时间复杂度计算示例4

2.1.1.5时间复杂度计算示例5

2.1.1.6时间复杂度计算示例6

2.1.1.7时间复杂度计算示例7

2.1.2空间复杂度

2.1.1.1空间复杂度计算示例1

2.1.1.2空间复杂度计算示例2

2.2常见复杂度对比

2.3复杂度笔试题

在之前的博文中，我们基本介绍完了C语言的语法知识，例如分支循环，指针和结构体等知识，今天我们终于要进入到学习数据结构的知识殿堂中，一起加油！！！

1.数据结构与算法

1.1数据结构介绍

数据结构是什么，它对我们有什么用处，我们为什么要学习它？抱着这样的疑问，我们先来介绍数据结构的概念。

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有用途都有用，所以我们要学各式各样的数据结构，

如：线性表、树、图、哈希等

数据结构，数据与结构，其实就是各种数据结合形成了不同的结构，数据本身是离散的、无组织的，而通过不同的结构设计，我们可以将数据以特定方式组织起来，从而实现高效的存储、访问和操作。在C语言中，结构体（struct）和指针（*）是实现复杂数据结构的关键工具。我们接下来学习每一种数据结构基本都要用到这两项工具，所以结构体和指针的知识一定要掌握扎实。

1.2算法介绍

什么是算法？
用通俗的话说，算法就是解决问题的明确步骤。就像烹饪食谱一样，算法规定了一系列操作，将输入（如食材）通过有限步骤转化为输出（如菜肴）。在编程中，程序就是一道道算法的具体体现。

我们之所以学习数据结构就是为了学习优质的算法解决问题，比如数组，他帮助我们将一类数据连续存储在内存中，方便我们查找，修改，销毁。利用结构的优势设计出高效的设计，减少冗余代码。

2.算法效率

如何衡量一个算法的好坏呢？

我们来看一个题：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。这个代码的实现并不难，我们只需要循环 k 次将数组所有元素向后移动一位就行了，代码如下：

void rotate1(int* arr, int sz, int k)
{for (int i = 0; i < k; i++)//循环k次{int tmp = arr[sz-1];for (int j = sz - 1; j > 0; j--)//数组元素向后移动一位{arr[j] = arr[j - 1];}arr[0] = tmp;}
}int main()
{int arr[5] = { 1,2,3,4,5 };int sz = sizeof(arr) / sizeof(arr[0]);int k = 0;scanf("%d", &k);rorate(arr, sz, k);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

上面这个代码已经可以满足题目的要求，但是有没有感觉这个程序的效率太低了，如果 k 值很大并且数组长度很长，那么这个循环简直不敢想象会进行多少次，有没有办法优化一下，经过观察，我们可以发现，如果 k 值等于数组长度的时候，旋转完后相当于没有旋转，所以我们可以这样改进：

void rotate2(int* arr, int sz, int k)
{int new_arr[5];//将排好的数组先存入新数组中for (int i = 0; i < sz; i++){new_arr[(i + k) % sz] = arr[i];//不管k为多大，(i+k)%sz都不会大于sz}for (int i = 0; i < sz; i++){arr[i] = new_arr[i];}
}

rorate2 和 rorate1 实现效果相同，但在效率上要比 rorate1 强上很多，重复代码运行次数大大减少，那到底好多少呢？有没有一个定义，当然有，接下来我们就要引进复杂度的概念。

2.1复杂度

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

时间复杂度主要衡量⼀个算法的运行快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。(并不是完全不重重，是相对时间来说的)

2.1.1时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，那么 为什么不去计算程序的运行时间呢 ？

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。

2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。

3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的 执行次数 。通过c语⾔编译链接章节学习，我们知道算法程序被编译后⽣成⼆进制指令，程序运⾏，就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执行次数和运行时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决⼀个问题的算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b。

我们来看一个案例：

实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来是很麻烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变⼤时T(N)的差别，上面我们已经看到了 当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

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

推导大O阶规则

1. 时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，

低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。

2. 如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数

对结果影响越来越小，当N无穷大时，就可以忽略不计了。

3. T(N)中如果没有N相关的项目，只有常数项，⽤常数1取代所有加法常数。

通过以上方法，可以得到 Func1 的时间复杂度为： O(N^2 )

2.1.1.1时间复杂度计算示例1

// 计算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);
}

Func2执⾏的基本操作次数：

T ( N ) = 2 N + 10

根据推导规则第2条和第3条得出

Func2的时间复杂度为： O ( N )

2.1.1.2时间复杂度计算示例2

// 计算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);
}

Func3执⾏的基本操作次数：

T ( N ) = M + N

在这里M和N都是变量，我们并知道它们的大小，所以并不能轻易删去任何一个

Func2的时间复杂度为： O(M+N)

如果M>>N，那么时间复杂度为O(M)

如果M<<N，那么时间复杂度为O(N)

如果M==N，那么时间复杂度为O(M+N)(并不是完全相等，是对计算机来说指M和N的差值并不大)

2.1.1.3时间复杂度计算示例3

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

Func4执⾏的基本操作次数：

T ( N ) = 100

根据推导规则第1条得出

Func2的时间复杂度为： O (1)

注意：无论这里执行次数是一万还是一亿，最后的时间复杂度都是O(1)

2.1.1.4时间复杂度计算示例4

// 计算strchr的时间复杂度？
const char* strchr(const char* str, int character)
{const char* p_begin = s;while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;
}

注意：这个代码的时间复杂度为多少取决于他要找的那个字符在字符串的什么位置。

strchr执⾏的基本操作次数：

1）若要查找的字符在字符串第⼀个位置，则： T ( N ) = 1

2）若要查找的字符在字符串最后的⼀个位置，则： T ( N ) = N

3）若要查找的字符在字符串中间位置，则： T ( N ) = N/2

因此：strchr的时间复杂度分为：

最好情况： O (1)

最坏情况： O ( N )

平均情况： O ( N )

大O的渐进表示法在实际中⼀般情况取的是算法的上界，也就是最坏运行情况。

所以strchr的时间复杂度为O(N)

2.1.1.5时间复杂度计算示例5

// 计算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-1次比较，T(N)=N

如果数组有序但为降序，则需要进行n-1轮比较，第k轮需要比较n-k次，所以T(N)=(n*(n-1))/2

取平均情况,则进行约n^2/2次比较，T(N)=n^2/2

因此：BubbleSort 的时间复杂度分为：

最好情况： O (N)

最坏情况： O ( N^2 )

平均情况： O ( N^2 )

2.1.1.6时间复杂度计算示例6

// 计算Func5的时间复杂度？
void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

当n=2时，执⾏次数为1

当n=4时，执⾏次数为2

当n=16时，执⾏次数为4

假设执⾏次数为 x ，则 2 ^x = n

因此执⾏次数： x = log2 n

因此：func5的时间复杂度取最差情况为：

O (log 2 n )

注意log2 n 、 log n 、 lg n 的表表示

当n接近无穷大时，底数的大小对结果影响不大。因此，⼀般情况下不管底数是多少都可以省略不 写，即可以表示为 log n 不同书籍的表示方式不同，以上写法差别不大，我们建议使用 log n

2.1.1.7时间复杂度计算示例7

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

调⽤⼀次Fac函数的时间复杂度为 O (1)

⽽在Fac函数中，存在n次递归调⽤Fac函数

因此：

阶乘递归的时间复杂度为： O ( n )

我们需要掌握一些简单程序的时间复杂度的计算方法，以上示例都比较重要，需要自己能够独立算出。

2.1.2空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是计算程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很⼤，所以空间复杂度算的是变量的个数。

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

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

2.1.1.1空间复杂度计算示例1

// 计算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额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间

因此空间复杂度为 O (1)

2.1.1.2空间复杂度计算示例2

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

Fac递归调⽤了N次，额外开辟了N个函数栈帧，每个栈帧使⽤了常数个空间

因此空间复杂度为： O ( N )

2.2常见复杂度对比

2.3复杂度笔试题

这个题在我们介绍复杂度的时候已经解答过，但是我们看该题的进阶，使用复杂度为O(1)的原地算法解题？这是什么意思呢？我们先将rotate1和rotate2两个函数拿过来，根据前面所学的知识，计算一下它们的时间复杂度和空间复杂度。

//申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中
void rotate2(int* arr, int sz, int k)
{int new_arr[5];//将排好的数组先存入新数组中for (int i = 0; i < sz; i++){new_arr[(i + k) % sz] = arr[i];//不管k为多大，(i+k)%sz都不会大于sz}for (int i = 0; i < sz; i++){arr[i] = new_arr[i];}
}//循环K次将数组所有元素向后移动⼀位
void rotate1(int* arr, int sz, int k)
{for (int i = 0; i < k; i++)//循环k次{int tmp = arr[sz-1];for (int j = sz - 1; j > 0; j--)//数组元素向后移动一位{arr[j] = arr[j - 1];}arr[0] = tmp;}
}

经过计算，得出：

	rotate1函数	rotate2函数
时间复杂度	O(N^2)	O(N)
空间复杂度	O(1)	O(N)

我们可以看到 rotate1 函数的空间复杂度为O(1)，但是时间复杂度为O(N^2)，而 rotate2 函数的时间复杂度仅为为O(N)，但是空间复杂度却为O(N)，有没有一种算法可以将时间复杂度控制为O(N)，空间复杂度又为O(1)呢？

void reverse(int* arr, int begin, int end)
{while (begin < end) {int tmp = arr[begin];arr[begin] = arr[end];arr[end] = tmp;begin++;end--;}
}void rotate3(int* arr, int sz, int k)
{k = k % sz;reverse(arr, 0, sz - k - 1);reverse(arr, sz - k, sz - 1);reverse(arr, 0, sz - 1);
}