【数据结构篇】时间复杂度

一.数据结构前言

 1.1 数据结构的概念

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

1.2 算法

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

二.时间复杂度

2.1 复杂度的概念

    算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好 坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度

    时间复杂度主要衡量 ⼀个算法的运⾏快慢 ，⽽空间复杂度主要衡量 ⼀个算法运⾏所需要的额外空 间 。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度非常在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法 的空间复杂度

2.2 时间复杂度的定义

    在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间（实际上，时间复杂度的本质是，随着输入规模的不断增大，算法运行速度的变化趋势），时间复杂度是描述程序的时间效率，那么为什么不去计算程序的运行时间那？

    1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。

    2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。

    3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估

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

（1）若要查找的字符在字符串第⼀个位置，则：

                 T (N) = 1

（2）若要查找的字符在字符串最后的⼀个位置， 则：

                 T (N) = N

（3）若要查找的字符在字符串中间位置，则：

                 T (N) = 2 / N

  因此：strchr的时间复杂度分为：

  最好情况： O ( 1 )

  最坏情况： O ( N )

  平均情况： O ( N / 2 )

为啥关注算法的最坏情况，你可以这样理解：某一天你和女朋友约好下班后去约会看晚上 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

 

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