学步园

在计算算法的时间复杂度时，我们一般采用BigO函数。BigO函数中只保留最有价值的函数组成部分，去掉系数，去掉常数。例如：O(a*n^2+b*n+1)=O(n^2)。同时我们在算法分析时会尽量选择最接近的BigO函数。比如快速排序(QuickSort)和归并(MergeSort)的算法时间复杂度的上限可以是O(n^2)，也可以是O(n*lgn)，但我们会选择O(n*lgn)，因为它最接近。

简单的算法，很多时候，通过直觉我们就可以得出它的时间复杂度。比如看到下面的语句，如果doSomething时间复杂度是O(1)，那么整个算法的时间复杂度是O(n^2)。

for i in range(n):
    for j in range(n):
        doSomething2

看到下面的语句，那么整个算法的时间复杂度是O(n)。

for i in range(n):
    doSthing1

但有时直觉是不对的，比如桶排序算法，里面有双重循环，但算法的时间复杂度实际上是线性的。在详细研究桶排序算法之前，我们需要首先掌握如何分析while(或for)循环的时间复杂度。例如下面的算法：

while S1:
    S2

S1和S2可以是时间复杂度非O(1)的复合语句。假如这个循环的执行次数是n，那么S2语句将会执行n次，S1语句会执行n+1次。(for循环同理)，那么整个算法的时间复杂度就是O(S1*(n+1))或者O(S2*n)，取两者的最大值。对于简单的算法S1*(n+1)无意义，例如下面的算法，时间复杂度O(n+1)=O(n)。但在复杂的算法，如桶排序算法中，O(n+1)中的常数1就有意义。

for i in range(n):
    i+1

下面是桶排序算法。首先凭直觉，第12和13行是双重循环，外重循环次数m，内重循环buckets[j]的最大值可能为n，那么算法的时间复杂度是O(m*n)；但实际它不是最接近的BigO函数。我们详细分析一下。因为总共只有n个元素，实际上第14行只会执行n次。再看13行，内层循环执行(buckets[j]+1)次，外层循环执行m次，那么整个12和13行会执行的次数为(buckets[0]+1)+(buckets[1]+1)+...+(buckets[m-1]+1)=n+m。所以整个算法的时间复杂度是O(m+n)，而不是直觉的O(m*n)。

01 
02 import random
03 
04 def bucketSort(alist, n, buckets, m):
05     for i in range(m):
06         buckets[i]=0
07 
08     for i in range(n):
09         buckets[alist[i]] += 1
10 
11     i=0
12     for j in range(m):        
13         for k in range(buckets[j]):
14             alist[i]=j
15             i+=1
16 
17 if __name__ == '__main__':
18     m=10
19     n=40
20     alist=[random.randrange(0,m) for i in range(n)]
21     buckets=[0] * 10
22     print('before sort')
23     print(alist)
24     bucketSort(alist,n,buckets,m)
25     print('after sort')
26     print(alist)
27 
28 

下面是桶排序算法一次执行的输出结果。桶排序只适合特定类型的排序。

before sort
[7, 1, 6, 4, 6, 0, 2, 9, 3, 9, 6, 3, 9, 1, 5, 1, 1, 6, 0, 8, 2, 0, 1, 0, 7, 9, 1, 5, 7, 8, 7, 4, 7, 0, 0, 7, 8, 8, 9, 3]
after sort
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9]

参考文献：

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

P.S.正文部分到此结束，前面Python程序的行号由下面程序生成，是我以前写的一个程序，留个纪念。

import java.util.*;
import java.io.*;

public class Number{
    public static void main(String[] args ) throws Exception{
        long start=System.currentTimeMillis();
        System.out.println ("start time:"+start);
        if(args.length!=2) 
        {
            System.out.println("usage: java Number <infile> <outFile>");
            return;
        }
        BufferedReader inReader = new BufferedReader(new FileReader(args[0]));
        BufferedWriter outWriter = new BufferedWriter(new FileWriter(args[1]));
        int count=0;
        String line=null;
        do{
            line = inReader.readLine();
            if(line!=null){
                count++;
            }
            else{
                break;
            }
        }
        while(true);

        if(count<=0) {
            System.out.println(args[0] + " has zero line");
            return;
        }
        String strCount=Integer.toString(count);
        //System.out.println("strCount=" +strCount);
        int width = strCount.length();
        //System.out.println("width=" +width);
        inReader.close();
        count=0;
        inReader = new BufferedReader(new FileReader(args[0]));
        do{
            line = inReader.readLine();
            if(line!=null){
                count++;
                line = addLeadingZero(Integer.toString(count),width) + " " +line ;
                outWriter.write(line,0,line.length());
                outWriter.newLine();
            }
            else{
                break;
            }
        }
        while(true);

        inReader.close();
        outWriter.close();
        long end=System.currentTimeMillis();
        System.out.println ("end time:"+end);
        System.out.println ("total second:"+(end-start)/1000);
    }

    public static String addLeadingZero(String str,int width){
        int len = str.length();
        if(len>=width) return str;
        width = width - len;
        StringBuilder b=new StringBuilder(str);
        for(;width>0;width--)
        {
            b.insert(0,'0');
        }
        return b.toString();
    }
}