文章目录
前言
本节内容讲解数据结构中的复杂度。在认识复杂度之前，我们先了解数据结构和算法的定义。
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。数据结构有各式各样的，且没有任何一种单一数据结构对所以用途都有用，如线性表、树、图、哈希等。
算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。一、复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。 因此衡量一个算法的好 坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 时间复杂度主要衡量⼀个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的 迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法 的空间复杂度。 下面讲解力扣上面一道题，带大家深入了解复杂度对算法的重要性。 题目描述：给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释: 向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
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 + 2 ∗ N + 10 • N = 10 ---T(N) = 130 • N = 100 ----T(N) = 10210 • N = 1000 T----T(N) = 1002010当N越大，T (N)越大，就会发现函数式T (N)中常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示常使用大O的渐进表示法。
1.大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。推导大O阶规则 ： 1. 时间复杂度函数式T(N) 中，只保留最高阶项，去掉那些低阶项，因为当 N 不断变大时， 低阶项对结果影响越来越小，当 N无 穷大时，就可以忽略不计了。 2. 如果最高阶项存在且不是 1 ，则去除这个项目的常数系数，因为当 N 不断变大，这个系数 对结果影响越来越小，当 N无 穷大时，就可以忽略不计了。 3. T(N) 中如果没有 N相 关的项目，只有常数项，用常数 1 取代所有加法常数。通过对大O方法的认识，上面的案例Func1的复杂度为 O(N² )
2.时间复杂度计算示例
示列1：
计算Func2的时间复杂度
// 计算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);
}// 计算Func3的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}解释：
Func3执行的基本操作次数： 在for语句中，要执行100次操作，则T ( N) = 100，又因为规则的第三条则Func3的时间复杂度为： O(1) . 注：O(1)里面的1并不是指该程序执行1次，而表示常数；且无论常数是多少，常数对时间的增加趋势是没有任何影响。示列3：
计算 strchr 的时间复杂度（找某个字符串在字符中出现的位置）// 计算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 )总结 通过上面 示列3 我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。 最坏情况： 任意输入规模的最大运行次数(上界) 平均情况：任意输入规模的期望运行次数 最好情况：任意输入规模的最小运行次数(下界) 大O的渐进表示法在实际中一般情况关注的是算法的上界，也就是最坏运行情况。
示列4：
void func3(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}三、空间复杂度
空间复杂度也 是一个数学表达式 ， 是对一个算法在运行过程中因为算法的需要额外临时开辟的空间 。 空间复杂度不是程序占用了多少字节的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 注意：函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了， 因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。1.空间复杂度计算示列
示列1：
计算 BubbleSort 的时间复杂度和空间复杂度// 计算BubbleSort的时间复杂度和空间复杂度
void bubble_sort(int* arr, int sz)
{
int i = 0;
int j = 0;
for (i = 0; i < sz - 1; i++)
{
int flag = 1;//假设每一趟已经有序
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])//升序
{
flag = 0;//表示无序
//对数组中的整型数据交换
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
//判断是有序，直接退出
if (flag == 1)
{
break;
}
}
}解释：
假设数组有n个整型数据，第一个数执行次数为n-1次，第二个数执行次数为n-2次.....以此类推则最后一个数执行次数为1次，则n-1+n-2+n-3+...+1;由等差数列求和公式得Tn=N(N-1)/2，所以时间复杂度O(N^2) ，空间复杂度是函数在运行时申请的额外空间，则空间复杂度O(1)
示列2：
//计算阶乘递归Fac时间复杂度和空间复杂度
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}解释：
调用一次Fac函数的时间复杂度为 O (1)，调用N次Fac函数的时间复杂度为 O(N)函数调用一次就会创建一个函数栈帧，函数栈帧就会申请空间，所以Fac递归调用了N次，额外开辟了N个函数栈帧，则额外申请N-1个空间，所以空间复杂度O(N)
在这里简单了解一下常见复杂度之间的对比：
以上是时间复杂度和空间复杂度的介绍，内容不是很完善，有不足的地方请多多指教。
标签：int,复杂度,++,算法,时间,空间,数据结构 From： https://blog.csdn.net/2402_86630696/article/details/142864285