《大话数据结构》笔记-day1

函数的渐进增长

算法随着n的增大

可以忽略加法常数
可以忽略与最高次项相乘的的常数
最高次项的指数越大,结果增长越快

判断一个算法的效率

函数中的常数和其他次项常常可以忽略,更应该关注主项(最高阶项)的阶数

事前估算方法

某个算法,随着n的增大,它会越来越优于另一种算法,或者越来越差于另一算法

算法时间复杂度

T(n) = O(f(n))
一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法

推导大O阶方法

		1.用常数 1 取代运行时间中的所有加法常数
		2.在修改后的运行次数函数中,只保留最高阶项
		3.如果最高阶项存在且不是 1 ,则去除与这个项相乘的常数
		最后得到的就是大O阶

常数阶

与问题的大小无关(n的多少),执行时间恒定的算法
对于分支结构,无论真假,执行次数都是恒定的,不会随着n的变大而发生变化,单纯的分支结构(不包含在循环结构中),时间复杂度也是O(1)

个人总结:单条语句,只执行一次

线性阶

要确定某个算法的阶次,我们常常需要确定某个特定语句或某个语句集运行的次数
分析算法的复杂度,关键就是要分析循环结构的运行情况

循环的时间复杂度 == 循环体的复杂度 × 该循环运行的次数	

常见时间复杂度

O(1) < O(logn) < O(n) <O(nlogn) <O( n2) <O(n3) <O(2n) <O(n!) <O(nn)

最坏情况与平均情况

  • 最坏情况运行时间是一种保证,那就是运行时间将不会再坏了。在应用中,这就是一种最重要的需求。通常,除非特别指定,我们提到的运行时间都是最坏情况的运行时间
  • 平均运行时间是所有情况中最有意义的,因为它是期望的运行时间
  • 平均时间复杂度:计算所有情况的平均值
  • 最坏时间复杂度:计算最坏情况的时间复杂度。
    一般在没有特殊说明情况下,都是指最坏时间复杂度

算法空间复杂度

算法空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度公式
S(n)= O(f(n))

线性表

线性表:零个或多个数据元素的有限序列
线性元素的个数n定义为线性表的长度,n=0时,称为空表
在较为复杂的线性表中,一个数据元素可以由若干个数据项组成

    原文作者:AriesZzz
    原文地址: https://blog.csdn.net/AriesZzz/article/details/91982359
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞