算法读书笔记-01-算法分析

1. 数学模型

1.1 近似

N<sup>3</sup>/6-N<sup>2</sup>/2+N/3 \~ N<sup>3</sup>/6。使用 ~f(N) 来表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。

1.2 增长数量级

N³/6-N²/2+N/3 的增长数量级为 O(N³)。增长数量级将算法与它的具体实现隔离开来，一个算法的增长数量级为 O(N³) 与它是否用 Java 实现，是否运行于特定计算机上无关。

1.3 内循环

执行最频繁的指令决定了程序执行的总时间，把这些指令称为程序的内循环。许多程序的运行时间都只取决于其中的一小部分指令。

1.4 成本模型

使用成本模型来评估算法，根据内循环的操作来确定成本模型。

2. 注意事项

2.1 大常数

在求近似时，如果低级项的常数系数很大，那么近似的结果是错误的。

2.2 缓存

计算机系统会使用缓存技术来组织内存，在这种情况下访问大数组中若干个并不相邻的元素所需的时间可能比访问相邻元素慢的多。

2.3 处理对输入的依赖

对最坏情况下的性能的保证

理论研究者们要从极度悲观的角度来估计算法的性能。

在核反应堆、心脏起搏器或者刹车控制器中的软件，最坏情况下的性能是十分重要的。

随机化算法

通过打乱输入，去除算法对输入的依赖。

均摊分析

将所有操作的总成本除于操作总数来将成本均摊。

例如对于动态的调整数组大小的栈数据结构来说：

空栈进行 N 次连续的 push() 调用需要访问数组的次数为 N+4+8+16+…+2N=5N-4（N是向数组写入元素的次数，也就是N次push()的调用，其余都是调整数组大小时进行复制需要访问数组的次数）

3. ThreeSum 问题

ThreeSum 用于统计一个数组中和为 0 的三元组数量。

public interface ThreeSum {
    int count(int[] nums);
}

3.1 ThreeSumSlow

该算法的内循环为 if (nums[i] + nums[j] + nums[k] == 0) 语句，总共执行的次数为 N(N-1)(N-2) = N³/6-N²/2+N/3，因此它的近似执行次数为 ~N³/6，增长数量级为 O(N³)。

public class ThreeSumSlow implements ThreeSum {
    @Override
    public int count(int[] nums) {
        int N = nums.length;
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0){
                        cnt ++;
                    }
                }
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
        ThreeSumSlow slow = new ThreeSumSlow();
        int[] a = {-1,1,0,3,5,8};

        int count = slow.count(a);
        System.out.println(count);
    }
}

3.2 ThreeSumBinarySearch

将数组进行排序，对两个元素求和，并用二分查找方法查找是否存在该和的相反数，如果存在，就说明存在和为 0 的三元组。

应该注意的是，只有数组不含有相同元素才能使用这种解法，否则二分查找的结果会出错。

该方法可以将 ThreeSum 算法增长数量级降低为 O(N²logN)。(因为语言自带的排序是log（n）的时间复杂度)

import java.util.Arrays;

public class ThreeSumBinarySearch implements ThreeSum {
    @Override
    public int count(int[] nums) {
        Arrays.sort(nums);
        int N = nums.length;
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int target = -nums[j] - nums[i];
                int index  = BinarySearch(nums,target);
                // 应该注意这里的下标必须大于j，否则会重复统计
                if (index > j){
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public  int BinarySearch(int[] nums,int target){
        int l = 0;
        int h = nums.length - 1;
        while (l <= h){
            int m = l + (h-l)/2;
            if (target == nums[m]){
                return m;
            }
            else if (target >= nums[m]){
                l = m + 1;
            }
            else{
                h = m - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        ThreeSumBinarySearch binarySearch = new ThreeSumBinarySearch();
        int[] a = {-1,1,0,3,5,8};

        int count = binarySearch.count(a);
        System.out.println(count);
    }

}

3.3 ThreeSumTwoPointer

更有效的方法是先将数组排序，然后使用双指针进行查找，时间复杂度为 O(N²)。

同样不适用与数组存在重复元素的情况。

import java.util.Arrays;

public class ThreeSumTwoPointer implements ThreeSum {
    @Override
    public int count(int[] nums) {
        int N = nums.length;
        int cnt = 0;

        Arrays.sort(nums);
        for (int i = 0; i < N - 2; i++) {
            int l = i + 1;
            int h = N - 1;
            int target = -nums[i];
            while (l < h){
                int sum = nums[l] + nums[h];
                if (sum == target){
                    cnt ++;
                    l ++;
                    h --;
                } else if (sum < target){
                    l ++;
                }else {
                    h --;
                }
            }
        }
        return cnt;
    }
}

4. 倍率实验

倍率定理：

如果 T(N) ~ aN^blogN，那么 T(2N)/T(N) ~ 2^b。

例如对于暴力的ThreeSum算法，近似时间为 ~N³/6。进行如下实验：多次运行该算法，每次取的N值是前一次的两倍，统计每次执行的时间，并统计本次运行时间与前一次运行时间的比值，得到如下结果

N	Time(ms)	Ratio
500	48	/
1000	320	6.7
2000	555	1.7
4000	4105	7.4
8000	33575	8.2
16000	268909	8.0

public class RatioTest {

    public static void main(String[] args) {
        int N = 500;
        int loopTimes = 7;
        double preTime = -1;
        while (loopTimes-- > 0) {
            int[] nums = new int[N];
            StopWatch.start();
            ThreeSum threeSum = new ThreeSumSlow();
            int cnt = threeSum.count(nums);
            System.out.println(cnt);
            double elapsedTime = StopWatch.elapsedTime();
            double ratio = preTime == -1 ? 0 : elapsedTime / preTime;
            System.out.println(N + "  " + elapsedTime + "  " + ratio);
            preTime = elapsedTime;
            N *= 2;
        }
    }
}

public class StopWatch {

    private static long start;


    public static void start() {
        start = System.currentTimeMillis();
    }


    public static double elapsedTime() {
        long now = System.currentTimeMillis();
        return (now - start) / 1000.0;
    }
}

打赏