数据结构一

数据结构前言：

数据结构是指计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

算法前言：
算法就是定义良好的计算过程，简单来说，就是一系列的计算步骤，用来将输入数据转化为输出成果。

一、算法效率

算法在编成可执行的程序后，运行时需要消费时间和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

1.1 时间复杂度

定义：算法时间复杂度是一个函数式T（N），定量描述了算法运行的时间。但我们执行程序时，我们会发现当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

1.2 大O的渐进表示法

大O阶规则，时间复杂度函数中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果的影响越来越小，当N无穷大时，就可以忽略不计了。

由上图代码可知，T（N）= N^2 + 2 *N + 10;

用大O表示法，可以得到时间复杂度为O（N^2）

1.3 时间复杂度计算示例

• 示例1

func2的基本操作次数为T(N) = 2N+10

时间复杂度为O(N)

• 示例2

func3执行的基本操作符次数为T(N) = M + N

因此func3的时间复杂度为O(N)

• 示例3

T(N) = 100

时间复杂度为O(1)

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

• 示例4 

冒泡排序的时间复杂度

冒泡排序的逻辑为第一次执行N次，第二次执行N-1次........

若数组为有序情况下，T(N) = N。若数组有序且为降序的情况下T(N) = N *(N+1)/2;

因此冒泡排序的时间复杂度取最差情况为：O(N^2);

• 示例5

上述示例假设执行次数为x。

则2 ^ x = n

x = log(2)n;

因此时间复杂度为O(n) ;

注：当n接近无穷大时，底数的大小对结果影响不大。因此，一般情况下不管底数是多少都可以忽略不写，即可以表示为log n

• 示例6

调用一次函数的复杂度为O(1)

在此函数中，存在n此递归，因此阶乘递归的时间复杂度为O(N);

1.4 空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。空间复杂度计算规则基本跟时间复杂度相似，也用大O渐进表示法。

注：函数运行时所需要的栈空间（存储参数、局部变量、寄存器信息等）在编译期间已经确定好了

因此，空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

上述代码中，冒泡排序额外申请的空间有end 、exchange 、 t 等有限个局部变量，为常数个。因此空间复杂度为O（1）；

上述代码中，递归调用了N次，额外开辟了N个函数栈帧，每个栈帧使用了常数个空间

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

常见复杂度对比如下：

二、复杂度算法题

旋转数组

. - 力扣（LeetCode）

思路一：循环k次将数组所有的元素向后移动一位（代码不通过）

此方法的时间复杂度为O（N^2）

思路二：申请新的空间，先将后k个数据放到新的数组中，再将剩下的数据挪到新数组中。

此方法的空间复杂度为O(N),时间复杂度为O(N),相当于是用空间换时间。