算法复杂度(数据结构初阶)

欢迎大家来到我的博客，给生活来点impetus
今天我们学习的内容是数据结构初阶。

算法复杂度

一：数据结构前言

1.1数据结构

数据结构(Data Structure)是计算机存储、组织数据(增删查改操作)的⽅式，指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希等。
例如：在c语言部分，利用数组能够对数据进行增删查改，其实，数组就是一种数据结构。

1.2算法

算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。

1.3数据结构和算法的重要性

算法书籍推荐

二：算法效率

如何衡量⼀个算法的好坏呢？
案例：旋转数组在线oj，点击做题。
思路：循环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;}
}

代码点击执⾏可以通过，然⽽点击提交却⽆法通过，如下：

那该如何衡量其好与坏呢？

2.1复杂度的概念

算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

2.2复杂度的重要性

复杂度的考题在面试中很常见，如下：

三：时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式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的渐进表⽰法。

3.1大o的渐进表示法

⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号。

推导准则
1.时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项,，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

因为该方法衡量的是变化趋势，如果只有常数项，也就等价于增长趋势为0。

3.2时间复杂度的计算示例

通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
平均情况：任意输⼊规模的期望运⾏次数
最好情况：任意输⼊规模的最⼩运⾏次数(下界)
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

上述题目时间复杂度为o（n）。

注意书籍中log2n、logn 、lgn的表⽰.
当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤,。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表⽰为log n .
不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤log n

从上述例子总结一下：
计算时间复杂度只需看：
1：循环语句限制条件和变量调整
2：递归只需看次数和每次递归所用的时间复杂度

四：空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似，也使⽤⼤O渐进表⽰法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定,例如：没有申请空间等价于申请常量个变量。

4.1空间复杂度的计算示例

五：常见复杂度的对比

从上面的图形可知：这个图的增长趋势越大，复杂度越差，算法效率越差

六：复杂度算法题

6.1旋转数组

在线oj，点击做题
在这里存在三种思路：
方法一：时间复杂度O(n2 )
循环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;}
}

方法二：时间复杂度O(n)
申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

void rotate(int* nums, int numsSize, int k)
{int newArr[numsSize];//使用变长数组for (int i = 0; i < numsSize; ++i){ newArr[(i + k) % numsSize] = nums[i];//可以使得让一个数组的任意一个元素开始，逐渐往后去赋值给另一个数组}for (int i = 0; i < numsSize; ++i){ nums[i] = newArr[i];}
}

方法三：三次逆置
空间复杂度O(1)
• 前n-k个逆置：5 6 7 4 3 2 1
• 后k个逆置：4 3 1 7 6 5
• 整体逆置 5 6 7 1 2 3 4

代码如下：

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

结语

勇敢的人总是愿意拥抱生活中的每一个未知的挑战，有时表现无畏，有时表现坚定的信念，加油，陌生人！