估算算法时间复杂度的方法

估算算法时间复杂度的方法

就是根据程序运行的最基本的操作的次数，记为T（n）
例：算法：

　　for（i=1;i<=n;++i）

　　{

　　for(j=1;j<=n;++j)

　　{

　　c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n的平方 次

　　for(k=1;k<=n;++k)

　　c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n的三次方 次

　　}

　　}

　　则有 T（n）= n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级

　　则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c

　　则该算法的 时间复杂度：T（n）=O（n^3） 注：n^3即是n的3次方。

当然应该是o(n^2) ---------------------------------------------------------- 算法分析，就是复杂度的问题。 复杂度只算“最要命的”，比如，执行n^2的算法前来个快排根本不拖速度，n^2多的都豁出去了不在乎区区一个nlogn。 书里对复杂度进行了严格的定义，包括o()、o()、θ()、ω()四种符号。 简单地说， o(n^2)就是顶破天了搞个n^2次； o(n^2)就是天花板不到n^2，比n^2矮一点（比如希尔排序就是o(n^2)，因为它再倒霉也达不到n^2）； ω(n^2)就是说某个算法随便怎么至少都要耗费n^2，比如所有基于比较的排序都是ω(nlogn)； θ(n^2)就是说它即是o(n^2)又是ω(n^2)，被天花板和水泥地夹在中间了，动不了了，就是它了。