首页 > 编程语言 >算法的理解及其复杂度分析

算法的理解及其复杂度分析

时间:2024-07-25 11:57:44浏览次数:10  
标签:f1 f2 复杂度 T1 算法 理解 下界

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

相关文章