时间复杂度中的O(logN)

N的增长要快于log的任意的幂。对数（logN）最常出现的规律可概括为下列一般法则：如果一个算法用常数时间将问题的大小消减为其一部分（通常为1/2）（例如分治算法），那么该算法就是O(logN)。另一方面，如果使用常数时间只是把问题减少一个常数的数量（如将问题减少1），那么这种算法就是O(N)的。

 

时间复杂度中的O(logN)的例子

1.折半查找

给定一个整数X和整数A0，A1，···，AN-1，后者是已经预先排序并存在内存中，求下标i使得Ai=X，如果X不在数据中，则返回i=-1。

public static <T extends Comparable<? super T>> int binarySearch(T[] a, T x) {
        int low = 0, high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid].compareTo(x) < 0)
                low = mid + 1;
            else if (a[mid].compareTo(x) > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -1;
}

循环从high-low=N-1开始并在high-low<=-1结束。每次循环后high-low的值至少将该次循环前的值折半；于是，循环的次数最多为log(N-1)+2。（例如，若high-low=128，则在歌词迭代后high-low的最大值是64,32,16,8,4,2,1,0，-1）因此，运行时间是O(logN)。

 

2.欧几里得算法（辗转相除法）

计算最大公因数的欧几里得算法。两个整数的最大公因数（gcd）是同时整除二者的最大整数。

public static long gcd(long m, long n) {
        while (n != 0) {
            long rem = m % n;
            m = n;
            n = rem;
        }
        return m;
}

连续计算余数直到余数是0为止，最后的非零余数就是最大公因数。例如M=1989和N=1590，则余数序列是399,393,6,3,0，从而两者的最大公因数是3。

 

3.幂运算

public static long pow(long x, int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        if (isEven(n))
            return pow(x * x, n / 2);
        else
            return pow(x * x, n / 2) * x;
}