算法—时间复杂度

问题导读

1.什么是算法复杂度?
2.什么是空间复杂度？
3.什么是时间复杂度？
4.如何计算一个算法的时间复杂度？



1.算法复杂度
1.1.什么是算法复杂度?
算法复杂度分为时间复杂度和空间复杂度。其作用：

• 时间复杂度是指执行这个算法所需要的计算工作量；
• 而空间复杂度是指执行这个算法所需要的内存空间；
  

时间和空间都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少；

1.2.什么是空间复杂度？
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

固定部分:这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
可变空间:这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

1.3.什么是时间复杂度？
关于时间频度：
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n);

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。记为O(…)，也称为大O表示法；

另外，时间频度不同，但时间复杂度可能相同。如：T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2) //注意这里n2是n方的意思

时间复杂度去估算算法优劣的时候注重的是算法的潜力，也就是在数据规模有压力的情况之下（最坏情况）算法的执行频度，什么意思呢？比如2个算法，在只有100条数据的时候，算法a比算法b快，但是在有10000条数据的时候算法b比算法a快，这时候我们认为算法b的时间复杂对更优；

1.4.时间复杂度与空间复杂度的取舍问题
查阅了诸多资料，最后还是感觉这段解释比较靠谱，下面摘出这篇博客的观点：
https://blog.csdn.net/qiumengchen12/article/details/45697405

就目前来说，除了在一些特殊情况下，我们都是更加注重时间复杂度，而不是空间复杂度。注意，这里我们强调了，除了一些特殊情况外，有些特殊情况下，空间复杂度可能会更加重要。

那么，究竟什么时候应该着重考虑时间复杂度，什么时候应该着重考虑空间复杂度呢？我们来看一个例子：

设想现在需要由你来完成一个程序设计，程序要求是这样的：要求输入年份，返回该年份是否是闰年。

一提到这个问题，我想如果你学习过任何一门语言，你可能都做过类似的题目。你可能思路已经非常清晰了，满百除四百，不满除以4。

额，先不要急。我们来看看还能不能进一步提高性能，降低时间复杂度。也就是用空间复杂度来换取时间复杂度。比如，如果使用我们程序的用户，只会查看当前年份未来几年和过去几年的日历的话，我们完全可以使用一个比如：2100个元素的数组，每个元素为0或1，分别表示平年和闰年。这样当用户查询的时候，就不需要再进行复杂的逻辑判断，而只需要取出对应下标位置的元素即可。
反过来，如果我们的用户经常查询跨度上万年的日历信息（万年历），那么，我们肯定不能使用上面牺牲空间复杂度来换取时间复杂度的方案解决。因为如此巨大的空间消耗是我们损失不起的。

而，编程的精髓和美，并不在于一方的退让和妥协。而是在于如何在二者之间取一个平衡点，完成华丽变身。那么，对于我们这种程序应该如何权衡呢？

我想到的一种方案是：将与当前年份相近的几年存为固定数据，查询时只需要读取即可。而对于那些和当前年份相距较远的年份的数据，在用户请求查询时动态生成。

这样，既能在损失可接受空间的情况下，大幅度提高性能，又能保证空间的损失不至于太大而无法接受。我想当用户查询据今较远的数据时，有一些时间上的等待，也是可以接受的。

总结下这一段的核心思想：
不能简单的说时间复杂度就比空间复杂度重要，在特定场景下空间复杂度反而比时间复杂度重要，在程序中我们需要综合考虑让时间和空间的消耗达到一个平衡点，从上面平闰年计算的例子来看，我们可以缓存前后几年间的平润年，因为内存开销在可控范围内，至少是在现有条件下能够体验到的可接受范围，所以这几年的数据我们可以用增大空间消耗来减少时间的消耗，如果说要将一万年的所有平闰年数据都存上，那么即便是内存能撑得住也是得不偿失的，所以这时候我们用增大时间开销（网络请求，动态加载）去交换减少空间的开销（省去了万级数据的存储空间）； 所以综上，这就是个综合考量的问题；

另外我总是在想一个牛角尖问题，时间和空间都是算法复杂度的考量标准，但是现在说算法好坏好像更多的人关注的时间复杂度，空间复杂度却不去考虑，或者说空间复杂度不是那么重要？这是为什么呢？

上面也分析了，时间换空间或空间换时间都是根据现实情况来分析，而目前的现实情况就是，硬件内存这些东西的成本与极致的用户体验，比如更快的响应，操作的流畅感比起来，就目前的条件来看，重要程度是更低的，随着空间可接受度增大，时间可接受程度相对变小，说白了，就是现在空间条件宽裕了（各大设备厂家无脑怼硬件，说明目前空间资源成本相对较低），大家拼的就是速度，谁的算法执行快，谁的产品用户体验更好，谁在竞争中更有优势；

2.如何计算一个算法的时间复杂度？
算这个时间复杂度实际上只需要遵循如下守则：

用常数1来取代运行时间中所有加法常数；
只要高阶项，不要低阶项；
不要高阶项系数；

2.0:常见的时间复杂度：
按增长量级递增排列，常见的时间复杂度有：

• O(1)—常数阶
• O(N)—线性阶
• O(log2N)—对数阶
• O(nlogn)—线性对数阶
• O(n^2)—平方阶
  

2.1:O(1)—常数阶
O(1)的算法是一些运算次数为常数的算法。例如：


[mw_shl_code=bash,true]temp=a;
a=b;
b=temp;
[/mw_shl_code]

根据守则：
用常数1来取代运行时间中所有加法常数；
上面语句共三条操作，单条操作的频度为1，即使他有成千上万条操作，也只是个较大常数，这一类的时间复杂度为O(1)；

2.2:O(N)—线性阶
O(n)的算法是一些线性算法。例如：

[mw_shl_code=bash,true]  sum=0；                 
     for(i=0;i<n;i++)      
         sum++；[/mw_shl_code]

上面代码中第一行频度1，第二行频度为n，第三行频度为n，所以f(n)=n+n+1=2n+1。

根据守则：
只要高阶项，不要低阶项目，常数项置为1，去除高阶项的系数：
所以时间复杂度O(n)。这一类算法中操作次数和n正比线性增长。

2.3:O(log2N)—对数阶
什么是对数?
a^x = N,(a>0 && a!=1),那么x即是以a为底，N的对数，记作
其中a叫做对数的底数，N叫做真数。

例1:

[mw_shl_code=bash,true]    private static void 对数阶() {
        int number = 1;//执行1次
        int n = 100;//执行1次

        while (number < n) {
            number = number * 2; // 执行n/2次
            System.out.println("哈哈");//执行1次
        }

    }
[/mw_shl_code]

假设n为100，number是1，小于100退出循环。

• 第1次循环，number = 2，2^1。
• 第2次循环，number = 4, 2^2。
• 第3次循环，number = 8, 2^3。
• 第x次循环，number = 2^x
  

也就是2^x=n得出x=log&#8322;n。因此它的复杂度为O(logn)。

例2:
二分查找；
比如: 1,3,5,6,7,9；找出7
如果全部遍历时间频度为n；
二分查找每次砍断一半，即为n/2；
随着查询次数的提升，频度变化作表：


2.4:O(nlogn)—线性对数阶
上面看了二分查找，是LogN的（LogN没写底数默认就是Log2N)；
线性对数阶就是在LogN的基础上多了一个线性阶；
比如这么一个算法流程：
数组a和b，a的规模为n，遍历的同时对b进行二分查找，如下代码：


[mw_shl_code=bash,true]for(int i =0;i<n;i++)
    binary_search(b);
}[/mw_shl_code]

2.5:O(n^2)—平方阶
普通嵌套循环

[mw_shl_code=bash,true]    private static void 普通平方阶(){
        int n = 100;
        for (int i = 0; i < n; i++) {//执行n次
            for (int j = 0; j < n; j++) {//执行n次
                System.out.println("哈哈");
            }
        }
    }
[/mw_shl_code]

这种就是2层循环嵌套起来，都是执行n次，属于乘方关系，它的时间复杂度为O(n^2)。

等差数列嵌套循环

[mw_shl_code=bash,true]    private static void 等差数列平方阶() {
        int n = 100;
        for (int i = 0; i < n; i++) {//执行n次
            for (int j = i; j < n; j++) {//执行n - i次
                System.out.println("哈哈");
            }
        }
    }
[/mw_shl_code]

基本式：

i = 0，循环执行次数是 n 次。
i = 1，循环执行次数是 n-1 次。
i = 2，循环执行次数是 n-2 次。
…
i = n-1，循环执行的次数是 1 次。
换算式：

result = n + (n - 1) + (n - 2) … + 1
被加数递减，抽象为一个等差数列求n项和的问题，公差为1，带入公式，Sn = n(a1 + an ) ÷2
result = (n(n+1))/2
result = (n^2+n)/2
result = (n^2)/2 + n/2

粗略计算时间复杂度的三部曲：

1.去掉运行时间中的所有加法常数。
没有加法常数，不考虑。
2.只保留最高阶项。
最高阶参考上面列出的按增长量级递增排列，于是只需要保留result = (n^2)/2
3.如果最高阶项存在且不是1，去掉与这个最高阶相乘的常数得到时间复杂度
除以2相当于是乘以二分之一，去掉它，就得到，result = n^2， 所以这个算法的时间复杂度为O(n^2)。


3.时间复杂度的优劣对比
常见的数量级大小：越小表示算法的执行时间频度越短，则越优；

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

4.demo

https://github.com/zj614android/algorithm/blob/master/O.java