学习数据结构（1）时间复杂度

1.数据结构和算法

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

（2）算法就是定义良好的计算过程，取一个或一组的值为输入，并产生出一个或一组值作为输出，简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果

（3）算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量⼀个算法的运行快慢，而空间复杂度主要衡量⼀个算法运行所需要的额外空间

2.时间复杂度

（1）概念

在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率

为什么不去计算程序的运行时间？

·程序运行时间与编译环境、运行机器的配置有关，同一个算法程序，用一个老编译器进行编译和用新编译器编译，在同样机器下运行时间不同

·同⼀个算法程序，用⼀个老低配置机器和新高配置机器，运行时间也不同

·运行时间只能程序写好后测试，不能在程序写前通过理论思想计算评估

计算时间复杂度计算的不是程序的精确执行次数，（精确执行次数计算起来很复杂），计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别，只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法

（2）大O的渐进表示法

大O符号：是用于描述函数渐进行为的数学符号

规则：

·时间复杂度函数式T(N)中，只保留最高阶项，去掉低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了

·如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数对结果影响越来越小，当N无穷大时，就可以忽略不计了

·T(N)中如果没有N相关的项目，只有常数项，则用常数1取代常数

（3）实例

例1：计算Fucn1的时间复杂度

T(N)=N^2+2*N+10，只保留最高次项，则时间复杂度为O(N)

例2：计算Fucn2的时间复杂度

T(N)=2N+10，只保留最高次项，系数改为1，则时间复杂度为O(N)

例3：计算Fucn3的时间复杂度

T(N)=M+N，若M和N相差不大，T(N)可看成2N或2M，若M>>N，T(N)=M，若M<<N，T(N)=N，故时间复杂度为O(N)

例4：计算Fucn4的时间复杂度

T(N)=100，只有常数项，用1代替常数，则时间复杂度为O(1)

例5：计算Fucn5的时间复杂度

若要查找的字符在字符串第一个位置，T(N)=1，若要查找的字符在字符串最后一个位置，T(N)=N，若要查找的字符在字符串中间位置，T(N)=N/2或N/2+1（N是偶数），或T(N)=（N+1）/2（N是奇数），因此，Fucn5的时间复杂度分为：最好情况：O(1)，最坏情况：O(N)，平均情况：O(N)

补充：

有些算法的时间复杂度存在最好、平均和最坏情况

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

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

故例5的时间复杂度取O(N)

例6：计算BubbleSort的时间复杂度

若数组有序，则T(N)=N，若数组有序且为降序，则：T (N) = N(N-1)/2，故BubbleSort的时间复杂度取最差情况为O(N^2)

例7：计算Func6的时间复杂度

当n=2时，执行次数为1，当n=4时，执行次数为2，当n=16时，执行次数为4，假设执行次数为x ，则2^x= n， 因此执行次数：x = log (2) n，故Func6的时间复杂度为O(log (2) n)，当n接近无穷大时，底数的大小对结果影响不大，因此，一般情况下不管底数是多少都可以省略不写，即可以表示为log n，建议使用log n

例8：计算Fac的时间复杂度

递归算法的时间复杂度=单次递归的时间复杂度*递归次数

单次递归的时间复杂度为O(1)，递归次数为N，故Fac的时间复杂度为O(N)