算法复杂度和大O表示法
概念
算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。
时间复杂度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。
空间复杂度
空间复杂度是指算法在计算机内执行时所需存储空间的度量。
算法执行期间所需要的存储空间包括3个部分：
- 算法程序所占的空间；
- 输入的初始数据所占的存储空间；
- 算法执行过程中所需要的额外空间。
- 在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。
大O表示法
大O表示法用于描述算法的性能和复杂程度。当讨论大O表示法时，一般考虑的是CPU（时间的占用）。大O表示法是对算法性能的一种粗略估计，并不能够精准的反应某个算法的性能。打个比方，公司分为大公司、中等公司和小公司，而大中小就是对公司规模的粗略表示，并不能够准备的表示公司具体的大小。
分析算法时，时长遇到以下几类函数
下图比较了各个大O符号表示的时间复杂度
推导大O表示法的方式
- 用常量1取代运行时间中的所有加法常量；
- 在修改后的运行次数函数中，只保留最高阶项；
- 如果最高存在且不为1，则去除与这个项相乘的常数；
参考链接 https://www.jianshu.com/p/88a1c8ed6254
知乎：算法的时间和空间复杂度
女爷i
今天药忘吃喽~
╰+哭是因爲堅強的太久メ
还没有评论，来说两句吧...