时间复杂度

  之前认为时间复杂度就是程序执行的时间，百度上这么说的

算法的时间复杂度是一个函数，它定性描述该算法的运行时间

很多人包括我自己都有一个疑问，就是现在的计算机的硬件性能已经很强大了，所以对于性能或者说时间复杂度上还用关心吗，答案是需要的。 比如有这样一个例子，在一台很久的机器和一台处理性能高100倍的新机器，旧机器执行算法A时间复杂度为O(n),新机器执行算法B的时间复杂度为O(n2)。下面表格做下对比,因为性能差100倍，所以旧机器时间*100

可以看出来n 在100之前新机器运行时间比旧机器少，但是当n>100,甚至越来越大时，运行时间新机器已经比旧机器多了。 在实际开发项目上，这样的差距会被无限放大，成本就会体现出来。

大O表示法

在举一个例子 1、

for (int i = 0; i < 10; i++) {
      System.out.println("执行"+i+"次");
}

这个代码总会执行10次，所以时间复杂度表现为 T(n) = 10.

2、下面如果把10，换成变量n，则公式变为 T(n) = n.

3、再往下

for (int i = n; i > 1; i /= 2) {
      System.out.println("执行" + i + "次");
 }

执行次数 T(n) = logn 4、

for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("do something");
            }
        }

公式为T(n) = n2 针对上面场景时间复杂度的分析，有了渐进时间复杂度。

算法的渐进分析就是要估计：n逐步增大时资源开销T(n)的增长趋势

有如下几个原则：

• 如果运行时间是常数量级，用常数1表示；
• 只保留时间函数中的最高阶项；
• 如果最高阶项存在，则省去最高阶项前面的系数。

大O表示法，针对场景上面四种场景：

• T(n) = 10 可以表示为O(1)
• T(n) = n 可以表示为O(n),同样如果T(n) =5 n，也是如此
• T(n) = logn 可以表示为O(logn)
• T(n) = n2 可以表示为 O(n2)

O(1) < O(logn) < O(n) < O(n^2),当然除了这些还有更复杂的 O(nlogn)、O(n^3)、 O(m*n)、O(2^n)、O(n!)

所以判断一个算法的复杂度，使用大O表示法可以很直观的判断出来。