数据结构和算法2-近似记法

Big-O记法

一般用O（n）记法来渐进界定算法运行时间的常数函数边界。希望这个常数函数代表算法运行时间的上界。

在最差情况下二分法搜索的运行时间为O（lgn），认为在所有情况下二分法搜索的搜索时间为O（lgn）是错误的。

二分法搜索的时间从来不会超过O（lgn），多数情况下其搜索时间都会少于O（lgn）

一般算法中基本操作重复执行次数是问题规模n的某个函数，用T（n）表示，若有个辅助函数f（n）是T（n）的同数量级函数。记作T（n）=O（f（n）），即为算法的渐进时间复杂度，简称时间复杂度

T（n）=O（f（n））表示存在一个常数C，使得在n趋于无穷时总有T（n）<=C*f（n）。

Big-Theta记法

当n变得很大的时候，算法的运行时间介于k1•n和k2•n之间，其中k1和k2为常数

Big-Omega记法

有的算法只能描述其至少要运行多少时间而无法给出其运行时间的上限时使用，存在足够大的n，运行时间至少是k•f（n），其中k为常数。