总览

算法相关知识

算法复杂度

算法的时间复杂度和空间复杂度合称为算法的复杂度

时间复杂度

时间频度：在假设执行一个语句的时间是固定的情况下，一个算法的语句执行次数称为语句频度或时间频度，为 T(n)

时间复杂度：在刚才的时间频度中，n 是问题的规模，n 不断变化的时候，T(n)也会不断变化，我们想要知道它的规律的话，引入了时间复杂度的概念。就是对于随着 n 的不断变大，T(n)/f(n)为一个不等于 0 的常数。于是 f(n)就是 T(n)的同数量级函数。记做 T(n) = O(f(n))。O(f(n))就是算法的渐进时间复杂度。很多时间频度不同的时候，但是时间复杂度可能是相同的。

最坏时间复杂度：最坏情况下的时间复杂度，就是实例运行时间的上界，默认情况下就是大 O 了。

最好时间复杂度：最好情况下的时间复杂度，就是 Ω。

如果一个时间复杂度既是 O，又是 Ω，那就可以称为就是 Θ。

平均时间复杂度：就是所有的可能输入实例均以等概率出现的情况下，算法的期望运行时间。

(1)Θ（西塔）：紧确界。 相当于”=”

(2)O （大欧）：上界。 相当于”<=”

(3)o（小欧）：非紧的上界。 相当于”<”

(4)Ω（大欧米伽）：下界。 相当于”>=”

(5)ω（小欧米伽）：非紧的下界。 相当于”>”

空间复杂度

空间复杂度是指完成一个程序所需内存的大小。

利用程序的空间复杂度，可以对程序的运行需要的内存数有个预先估计。

数据结构

##

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 981909093@qq.com