初识数据结构--时间复杂度 和 空间复杂度
数据结构前言
数据结构
数据结构是计算机存储、组织数据的方式(指不仅能存储数据，还能够管理数据-->增删改)。指相互之间存在一种或多种特定关系的数据元素的集合。没有单一的数据结构对所有用途都有用，所以我们要学习各种的数据结构，比如：线性表、树、图、哈希等。
算法
其实算法就在我们身边。这就好像是给你一道题，怎么去实现它。
算法：就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为 输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。
算法效率
那么任何衡量一个算法的好坏呢？
案例：旋转数组
思路：循环K次将数组所有元素向后移动⼀位
void rotate(int* nums, int numsSize, int k) {
while(k--)
{
int end = nums[numsSize-1];
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i] = nums[i-1];
}
nums[0] = end;
}
}
代码在力扣点击执行可以通过，但是点提交却无法通过，那怎么衡量呢？
这就要给大家提出复杂度的概念。
复杂度的概念
算法在编写成为可执行程序后，运行时需要耗费时间资源和空间(空间)资源。因此衡量一个算法的好坏，一般是通过时间和空间俩个维度来衡量的，既时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的 迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法 的空间复杂度。
总的来说：虽然现在计算机的存储容量已经变的很大了，但是也不能随意的浪费。
时间复杂度
定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？
1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译 器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。
对于定义大家了解一下就行。
大家只要知道时间复杂度是用来计算程序的执行次数 。
案例：
// 请计算⼀下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 * N + 10
因为第一个for循环中还嵌套了一个for循环，就是当 i = 0 时， j 就要循环N次 ，当 i = 1， j 就要循环N次 ...... ，这样就是N²。
然后下一个for循环是和第一个for 循环时并列的，所以相加。
最后一个循环了10次，所以相加10。
影响时间复杂度的条件有：
每条语句的执行时间 * 每条语句的执行次数
但是每条语句的执行时间无法给出准确的数据。得出结论：每条语句的执行时间即使有差别，但是微乎其微，可以忽略不计，认为每条语句的执行时间是相同的。
实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很 ⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤。，所以我们只需要计算程序能代表增⻓量 级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。
Func1的时间复杂度为O(N²)。
时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时， 低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了
大O渐进表⽰法
1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时， 低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数 对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。
时间复杂度计算示例
示例1：
void Func2(int N)
{
int count = 0;
for (int i = 0; i < 2 * N; i++)
{
++count;
}
int m = 10;
while (m--)
{
++count;
}
}Func2执⾏的基本操作次数： T (N) = 2N + 10
根据推导规则第1条得出
Func2的时间复杂度为： O(N)
示例2：
void Func3(int M, int N)
{
int count = 0;
for (int i = 0; i < M; i++)
{
++count;
}
for (int k = 0; k < N; k++)
{
++count;
}
printf("%d\n", count);
}Func3执⾏的基本操作次数：
T (N) = M + N
因此：Func2的时间复杂度为： O(M + N)
因为在这边M 和 N都是变量，都得保留。
示例3：
void Func4(int N)
{
int count = 0;
for (int i = 0; i < 100; i++)
{
++count;
}
printf("%d\n", count);
}T (N) = 100
根据推导规则第3条得出
Func2的时间复杂度为： O(1)
示例4：
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的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。
空间复杂度
空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。
空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好 了，因 此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。
空间复杂度计算⽰例
⽰例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;
}
}函数栈帧在编译期间已经确定好了， 只需要关注函数在运⾏时额外申请的 空间。
BubbleSort额外申请的空间有 exchange等有限个局部变量，使⽤了 常数个额外空间
因此空间复杂度为 O(1)。
示例2：
long long Fac(int N)
{
if (0 == N)
{
return 1;
}
return Fac(N - 1) * N;
}Fac递归调⽤了N次，额外开辟了N个函数栈帧， 每个栈帧使⽤了常数个空间
因此空间复杂度为： O(N)
常见复杂度对比
大家可以看到当趋近于无穷时， n ! > 3 ^n > x² > ln(x) > sinx
希望对大家有所帮助。
原文地址：https://blog.csdn.net/2303_79266237/article/details/142714250
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！