1.什么是算法
算法(Algorithm)
一个有限指令集
接受一些输入(有些情况下不需要输入)
产生输出
一定在有限步骤之后终止
每一条指令必须:
有充分明确的目标,不可以有歧义
计算机能处理的范围之内
描述应不依赖于任何一种计算机语言以及具体的实现 手段
2.什么是好的算法
2.1空间复杂度 S ( n )
根据算法写成的程序在执行时 占用存储单元的长度。这个长度往往与输入数据的 规模有关。空间复杂度过高的算法可能导致使用的 内存超限,造成程序非正常中断。
2.2时间复杂度 T( n )
根据算法写成的程序在执行时 耗费时间的长度。这个长度往往也与输入数据的规 模有关。时间复杂度过高的低效算法可能导致我们 在有生之年都等不到运行结果。
在分析一般算法的效率时,我们经常关注下面 两种复杂度
最坏情况复杂度 Tworst( n )
平均复杂度 Tavg( n )
Tavg( n ) ≤ Tworst( n )
且由于平均情况复杂度较为难以估算,平时比较看重最坏情况复杂度。
3.复杂度的渐进表示法
上界: T( n) = O(f( n)) 表示存在常数C >0, n 0>0 使得当 n ≥ n 0 时有 T( n) ≤ C·f( n )
下界: T( n) = Ω (g ( n)) 表示存在常数C >0, n 0>0 使得当 n ≥ n 0 时有 T( n) ≥ C·g ( n )
既是上界又是下界: T( n) = Θ ( h ( n)) 表示同时有 T( n) = O( h ( n)) 和 T( n) = Ω ( h ( n))
由于一个函数的上界和下界有无穷多个,所以我们选择能找到的最小上界,以及最大下界来表示算法的复杂度(前提是能找到)。
3.1图示不同函数规模复杂度增长趋势
4.复杂度分析小窍门
若两段算法分别有复杂度 T1 ( n) = O(f1 ( n)) 和 T2 ( n) = O(f2 ( n)),则
二者平行: T1 ( n) + T2 ( n) = max( O(f1 ( n)), O(f2 ( n)) )
互相嵌套: T1 ( n) × T2 ( n) = O( f1 ( n) × f2 ( n) )
若 T( n )是关于 n 的 k阶多项式,那么 T( n)= Θ ( n^k )
一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else 结构的复杂度取决于if的条件判断复杂度 和两个分枝部分的复杂度,总体复杂度取三者中最大
标签:f1,f2,复杂度,T1,算法,理解,下界 From: https://blog.csdn.net/weixin_65866298/article/details/140668575