数据结构一
数据结构前言：
数据结构是指计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
算法前言：
算法就是定义良好的计算过程，简单来说，就是一系列的计算步骤，用来将输入数据转化为输出成果。
一、算法效率
算法在编成可执行的程序后，运行时需要消费时间和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
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)
常见复杂度对比如下：
二、复杂度算法题
旋转数组
思路一：循环k次将数组所有的元素向后移动一位（代码不通过）
此方法的时间复杂度为O（N^2）
思路二：申请新的空间，先将后k个数据放到新的数组中，再将剩下的数据挪到新数组中。
此方法的空间复杂度为O(N),时间复杂度为O(N),相当于是用空间换时间。
原文地址：https://blog.csdn.net/Rosillll/article/details/140289654
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！