• 推荐!搬瓦工官方代理,自动更换被封IPJust My Socks

ad

时间复杂度中的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;
}

 

点赞