算法时间复杂度计算

显示全部楼层 · 2018-9-12 16:37:51

本帖最后由剑弑于 2018-9-26 23:13 编辑

   算法！！！算法相信每一个软件工程师(程序员)都或多或少的接触的到，有时候甚至要自己去写。虽然写一个算法并不难，只要做到能够对一定规范的输入，在有限的时间内获得要求的结果输出就行；但我们所写的算法是否是最优最好的呢？我们该怎么去判断算法的好坏呢？当我们有好几种算法的实现该如何去选择最优的算法呢？时间复杂度！我相信很多都能答上来。对，就是时间复杂度！！！！！
   我们都知道每一个算法都有它自己的时间复杂度，但这个时间复杂度该怎么去计算呢？计算算法的时间复杂度就是我今天要跟大家分享的，也希望有对时间复杂度了解更深的大神指出我的不足。
   不同规模的输入需要的基本操作数是不相同的，如：一个排序算法排序10次跟排序100所需要的基本操作数必然是不同的。因此考虑算法输入规模的具体操作数即不现实也没必要。所以在算法分析中，可以建立以输入规模n为自变量函数T(n)来表示算法的时间复杂度；用大写O()来表示时间复杂度的写法（简称大O记法）。随着n的增大，T(n)增长最慢的为最优算法。
    大O推导法：

用常数1取代运行时间中的所有加法常数
在修改后的运行函数中，只保留最高阶项
如果最高阶项存在且不是1，则去除与这个项相乘的常数

时间复杂度的计算：
常数阶:O(1)

[C#] 纯文本查看 复制代码

string str = "Hello "; /*执行一次*/            str += "Work"; /*执行一次*/
            Console.WriteLine(str); /*执行一次*/

从代码中我们就能看到这个算法的运行次是3次，所以根据大O推导法应记为O(1)。

线性阶：O(n)

[C#] 纯文本查看 复制代码

string str = "Hello "; /*执行一次*/
            str += "Work"; /*执行一次*/
            int n = 100;/*执行一次*/
            for (int i = 0; i < n; i++)/*执行(n+1)次*/
            {
                Console.WriteLine(str); /*执行n次*/
            }

从代码注释可以看到算法的运行次数为 3+(n+1)+n=2n+4，根据大O推导法只保留最高阶项2n，去掉2n这个项的相乘常数，所以此算法的时间复杂度为O(n)。

   对数阶：O(log?(n))[?:表示底数]

[C#] 纯文本查看 复制代码

string str = "Hello "; /*执行一次*/
            str += "Work"; /*执行一次*/
            int n = 10,i=3;/*执行一次*/
            while (i>n)/*执行log3(n)+1次*/
            {
                i *= 3;/*执行log3(n)次*/
                Console.WriteLine(str);/*执行log3(n)次*/
            }

因为i每次的乘积是3，固i=3^x>n时循环结束，所以While运行次数为log3(n)+1；因此算法的运行次数为3+log3(n)+1+log3(n)+log3(n)=4+3log3(n)，根据大O推导法，保留最高阶项和去掉项的相乘常数，所以此算法的时间复杂度为O(log3(n))。

平方阶:O(n^2)

[C#] 纯文本查看 复制代码

 string str = "Hello "; /*执行一次*/
            str += "Work"; /*执行一次*/
            int n = 100,num=0;/*执行一次*/
            for (int i = 0; i < n; i++)/*执行n+1次*/
            {
                for (int j = 0; j < n; j++)/*执行n(n+1)次*/
                {
                    Console.WriteLine(str);/*执行n*n次*/
                }
            }

上面的程序是在内循环上加多一个外循环，从上面的线性阶我们就知道循环的时间复杂度为O(n)，所以在循环外加入外循环等于O(n*n)，固时间复杂度为O(n^2)。
注：如内外层循环次数不一样时，时间复杂度应为O(n*m)。

时间复杂度所耗时间：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) <O(2n) < O(n!) <O(nn)

心细的人可能会发现最后的几项时间复杂度没有说明，因为如果你的算法时间复杂度到了O(2n)你就应该考虑重新写过算法。