简单计算时间复杂度

@[toc]

一、简介

计算时间复杂度的3个出发点，掌握这三个出发点，那么一向搞不懂的时间复杂度就可以迎刃而解啦。

1. 找到执行次数最多的语句
2. 语句执行语句的数量级
3. 用O表示结果

然后：

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，那么我们就去除于这个项相乘的常数。比如3n^2我们取n^2

最后就可以得到你们想要的结果了。

二、时间复杂度：O（1）

我们来看一下这个例子，用的是java，内容就是打印8条语句，问这个程序的时间复杂度是多少？

public class TS {
    public static void main(String[] args) {
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
        System.out.println("111");
    }
}

O（8）？ 当然不是！！！按照时间复杂度的概念T（n）是关于问题规模为n的函数”，这里跟问题规模有关系吗？没有关系，用我们的第一个方法，时间复杂度为O（1）。

三、时间复杂度：O（n）(线性阶）

public class TS {
    public static void main(String[] args) {
        int sum = 0;
        for(int i=1;i<=100;i++) {
            sum = sum + i;
        }
    }
}

时间复杂度为O（n）。

四、时间复杂度：O（n^2）(平方阶）

public class TS {
    public static void main(String[] args) {
        int sum = 0;
        for(int i=1;i<=100;i++) {
            for(int j=1;j<=100;j++)
                sum = sum + i;
        }
    }
}

外层i的循环执行一次，内层j的循环就要执行100次，所以外层执行100次，那么总的就需要执行100*100次，那么n次呢？就是n的平方次了。所以时间复杂度为：O（n^2）。

平方阶的另外一个例子：

public class TS {
    public static void main(String[] args) {
        int sum = 0;
        for(int i=1;i<=100;i++) {
            for(int j=i;j<=100;j++)
                sum = sum + i;
        }
    }
}

当i=1的时候执行n次，当n=2的时候执行（n-1）次，......

一直这样子下去就可以构造出一个等差数列：n+（n-1）+（n-2）+......+2+1

根据等差数列的求和公式：

或者：

求和易得： n+n(n-1)/2整理一下就是n(n+1)/2然后我们将其展开可以得到n^2/2+n/2。

根据我们的步骤走，保留最高次项，去掉相乘的常数就可以得到时间复杂度为：O（n^2）

五、时间复杂度：O(log2n)（对数阶）

public class TS {
    public static void main(String[] args) {
        int i=1;
        int n= 100;
        while(i<n) {
            i = i*2;
        }    
}

2^x = n,所以时间复杂度为O(log2n)。

六、总结

补充常用的时间复杂度所耗费的时间从小到大依次是：

O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况：

平均运行时间： 是期望的运行时间。
最坏的运行时间： 是一种保证。我们提到的运行时间都是最坏的运行时间。