【数据结构篇】时间复杂度
一.数据结构前言
1.1 数据结构的概念
数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构， 如：线性表、树、图、哈希等
1.2 算法
算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果
二.时间复杂度
2.1 复杂度的概念
2.2 时间复杂度的定义
在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间（实际上，时间复杂度的本质是，随着输入规模的不断增大，算法运行速度的变化趋势），时间复杂度是描述程序的时间效率，那么为什么不去计算程序的运行时间那？
1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
3.3 大O渐进表示法（计算的）
那么，函数式 T (N) 到底是什么呢？因为算法的运行时间和基本语句执行次数成正比，精确计算执行次数很麻烦，且不同程序代码编译出的指令条数不同，精确计算意义不大，所以我们引入大 O 渐进法，它会去掉影响较小的项。下面具体描述大 O 渐进表示法的计算过程：
我在简略总结一下：
常数归一：将运行时间中的加法常数用 1 取代。
保留高阶：仅保留运行次数函数中的最高阶项。
去除系数：若最高阶项系数不为 1，去除该系数。
三.时间复杂度计算案例
3.1 示例1
T(N) = M+N
由于题目并没有说明M和N的具体大小，所以我们不能去掉其中的任意一项
时间复杂度O(M+N)
3.2 示例2
T(N) = 2*N + 10
先将 +10 变成 +1，由于 +10 为低阶项，去掉 +10 ，高阶项的系数不是1，将系数变为1
时间复杂度：O(N)
看到这我估计有人会想，为啥要去掉系数那，×2不是变化挺大的吗？那你想一想，如果输入规模趋于无穷大，那么给他×多少不是一样的吗
3.3 示例3
T(n) = 100
如果算法的基本操作执行次数是一个与输入规模无关的常数，那么其时间复杂度记为 O(1)
时间复杂度：O（1）（表示算法的基本执行次数和输入规模无关）
3.4 示例4
为啥关注算法的最坏情况，你可以这样理解：某一天你和女朋友约好下班后去约会看晚上 20:00 的电影，但是你手头有一项工作要完成，这项工作的任务量和难度是不确定的，所以你也不知道具体几点能结束工作出发去赴约。
现在你有三个时间点可以告诉她你大概能结束工作出发，分别是 17:00、18:00、19:00。考虑到工作可能出现各种意外状况，比如遇到复杂问题需要花费更多时间解决、中途可能有新的任务插入等，为了避免让女朋友等待，保证不会耽误看电影，你肯定会选择告诉她最晚的那个时间点 19:00。
这就如同在算法中，最坏情况代表着在任意输入规模下，算法运行的最大次数（上界）。我们关注最坏情况，是因为它能让我们在设计和评估算法时，知晓算法在最糟糕场景下的性能表现，确保算法在任何情况下都能满足一定的性能要求，就像告诉女朋友最晚时间能保证约会按时进行一样
3.5 示例5
若数组有序，只需要遍历一遍数组，所以他的时间复杂度是：O(N)
若数组有序且是降序，那么他要比较n-1趟，第一次比较n-1次 第二次比较n-2次 以此类推 到1次
所以他是一个等差数列，用等差数列求和公式计算是 :
首项是1 尾项是n-1 公差是1 一共有n-1项
用大O计算法进行表示：O（N^2）
3.6 示例6
3.7 示例7
我看过不少面经都对时间复杂度的计算进行了考察，这没有捷径，多练，多算，加油吧！！！