一.数据结构前言

 1.1 数据结构的概念

     数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构， 如：线性表、树、图、哈希等

1.2 算法

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

二.时间复杂度

2.1 复杂度的概念

 我在简略总结一下：

    常数归一：将运行时间中的加法常数用 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

 

 我看过不少面经都对时间复杂度的计算进行了考察，这没有捷径，多练，多算，加油吧！！！