系列文章目录

第一章 时间复杂度和空间复杂度

第二章 顺序表，列表

第三章 栈和队列

第四章 二叉树

第五章 排序

目录

系列文章目录

🏆文章目录

🏆前言

🏆一、算法的复杂度

🏆二、时间复杂度的概念

大0渐进

作者：🎈乐言🎈

简介：🎈大一学生，目前在致力于c/c++/python，高数的学习，有问题尽管问我，关注后私聊！

持续更新专栏：《c进阶》，《数据结构修炼》🚀（优质好文持续更新中）🎈

🏆前言

🏆一、算法的复杂度

算法在编写成可执行程序之后，需要花费时间资源和空间资源，而这正式衡量一个算法好坏的标准之一。因此衡量一个算法的复杂度，通常是由这两方面决定的，即是时间复杂度和空间复杂度

时间复杂度主要指的是代码运行的快慢

空间复杂度主要指的是代码运行所耗费的内存

我们需要注意的是，在经过计算机的迭代发展后，计算机的储存容量已经达到了很高的程度，所以我们应该更加注意时间复杂度，空间复杂度已经并没有那么重要了

🏆二、时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知 道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

例如以下的代码：

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;
}
printf("%d\\n", count);
}

当此时，我们明显可以发现count++执行了n^n+2*n+10次

n=10    N=130

n=100  N=10210

n=1000N=1002010

实际上我们计算时间复杂度的时候，并不需要如此精确，而是我们需要计算大概执行次数

我们通常使用大0渐进法

大0渐进

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

推导大O阶方法：

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

                                                                O(N^2)

此时，我们去掉了那些无关紧要的项，简洁明了的给出了执行次数

举例1：

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);
}

当此时，时间复杂度就显得扑朔迷离了，我们无法知道M和N的大小关系，所以我们只能写成

O(M+N)

举例2：

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\\n", count);
}

当此时，我们明显的可以看出这显然是常数次，我们规定所有常数次都写成

O(1)

举例3：

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);
}
// 计算Func3的时间

该代码我们则可以明显看出执行了2n+10次，而根据刚刚所学，10对于2n来说显得微不足道，直接去掉即可，而当此时n趋向于无穷大时（可以这么理解），n的倍数也显得微不足道了，因此也可以不写，所以该代码的时间复杂度为：

        O(N)

举例4：

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;}
}

当此时，冒泡排序的次数为n！，因此时间复杂度，不计算/2，不计算+-1，我们可以得出时间复杂度为:

O(N^2)

举例5

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;
else
return mid;
}
return -1;
}

则x=log2N

当我们暴力查找的时候，需要查找N次，差别巨大，二分查找是一个十分牛犇的算法

则该代码的时间复杂度为：

O(log2N)

举例6：

long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

该函数明显是递归实现

fac的函数被调用了n+1次，每次都是常数次，所以时间复杂度仍然是

O(N)

举例7：

long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);

这是一个斐波那契函数的递归，我们可以画图如下

二叉树的层数一直是乘以2，每个都是O(1)

所以该时间复杂度为等比数列 

为：2^0 +2^1 +2^2 +2^3+..............+2^(N-2）=2（1-2^(N-1))/(1-2)

所以该函数的时间复杂度为：

O(2^N)

三：空间复杂度的概念

举例1：
 

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;}
}

此处end，exchange都是常数个，所以的空间复杂度都是

O(1)

举例2

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;
}

此处malloc开辟了一个数组，由N+1个空间，所以空间复杂度为

O(N)

举例3：

long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}

此处涉及到函数栈帧的创建，如图所示：

 每个栈帧为常数个，且有n个栈帧，则有空间复杂度为;

O(N)

举例4：

long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

 他的空间复杂度为

O(N)

 函数递归的栈帧创建是往下创建的，再回来的时候会自动销毁，与原来的栈帧位于同一位置，所以该递归函数创建的栈帧仍然是N个，所以他的空间复杂度为：

O(N)

注意：     时间是不可以重复计算的

                空间是可以重复使用的

我们在调试窗口的调用堆栈，逐语句可以看出函数的调用堆栈的进程 

函数每次调用空间后销毁，并不是说这块空间不存在了，而是归还这块空间的使用权，内存是属于操作系统的，每次函数调用结束之后，会将空间的使用权归还，这块空间是永远存在的

类比：

进程           ------->垃圾桶

申请空间---------->扔垃圾

销毁内存----------->倒垃圾

越界/野指针----------->访问了不是属于自己的空间

🏆四：常见复杂度的对比

而这些复杂度的复杂程度也相差很大：；

🏆总结

本文主要讲解了时间复杂度和空间复杂度的内容，并且举例了例题讲解，需要老铁们继续加油，多做点题目积累，同时也希望大家多多支持，更多好文，敬请期待.........