学习内容来自清华计算机博士带你学习Python算法+数据结构。目前内容截止到树结构,后续的高级算法以后会补上。
算法概念简述
数据结构:数据存储
时间复杂度
每个电脑配置不一样。同一个程序执行的时间不同。
运行观察程序的快慢,耗时。
因此,选择一个公式来表示某一个程序执行的快慢。
估计算法运行效率与时间复杂度
内容
通俗理解O(1):
O:一个数学里式子上界的意思,这里简单理解为估计,大约,几1:类似单位,秒,分钟,小时。代码执行一次O(1)=运行时间:几秒
O(n):n重循环,执行n次。大约执行n秒。
由于时间复杂度是估计值:
O(3)的执行时间≈O(1)
O(n^2+n)的执行时间≈O(n ^ 2)
第一个式子,把常数当成一个单位,全为1.
第二个式子,取极限,留下最大的,在大时间面前,小时间可以忽略不计。
循环减半的过程会出现log(n)。
小结:
关于第二点:一般来说指的是,算法执行时间与设备和循环次数等有关。
这里n是大于1的。
判断时间复杂度
内容
如何快速判断时间复杂度: