大O表示法
2020-11-23 本文已影响0人
呀比是只鱼
时间复杂度
衡量一个算法可以从占用的空间和时间来评价其是否是一个更好的算法。这里主要从时间方面衡量。时间复杂度，可以看成是程序执行过程中所需要的运行步骤的计量，与用哪种语言无关。赋值语句包括了表达式计算和变量存储两个基本资源，程序设计中包含了3种控制流语句和赋值语句，而控制流语句仅作为组织语句，并没有实施处理。因此赋值语句的执行次数可以作为衡量算法时间的选择。
1. 问题规模是什么？
影响算法执行时间的主要因素。算法分析的目标是找出问题规模会怎么样影响一个算法的执行时间
2. 数量级函数
O(f(n))：f(n)为T(n)中主导的部分
基本操作数量函数T(n)的具体数值不重要，重要的是起决定因素的主导部分。用动态的眼光看，当问题规模增加时，T(n)中起主导部分的贡献超过其他部分的贡献。
例子：
, 对应
, 对应
仅保留最高阶项，去掉所有的系数
3.影响算法运行的时间
某些具体数据源也会影响算法运行的时间，杂乱无章的数据vs排序好的数据，在运行时差异很大。
分为最好、最差、平均情况，平均代表了主流。
分析算法时看主流，而不被某几个特定的运行状况迷惑。
4.常见的大O数量级函数
、
、
、
、
、
、
