A：（一）算法学习（CS-Notes）--2022.9.7算法分析

51 阅读 0 评论 34 点赞

我是靠谱客的博主英俊汉堡，最近开发中收集的这篇文章主要介绍A：（一）算法学习（CS-Notes）--2022.9.7算法分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法分析

数学模型

近似：类似于高数中的数量级？ $N^3/6 - N^2/3+N/2$ ~ $N^3/6$ ，使用 ~f(N) 来表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。
增长数量级也为O(N^3)
内循环：执行最频繁的指令决定了程序执行的总时间

注意事项

5.均摊分析

**将所有操作的总成本除于操作总数来将成本均摊。**例如对一个空栈进行 N 次连续的 push() 调用需要访问数组的次数为 N+4+8+16+…+2N=5N-4（N 是向数组写入元素的次数，其余都是调整数组大小时进行复制需要的访问数组次数），均摊后访问数组的平均次数为常数。

ThreeSum为例

ThreeSumSlow

粗暴方法解决，执行次数为N(N-1)(N-2)，近似执行次数为 $N^3/6$ ，增长数量级为O(N^3)

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;
    }
}

ThreeSumBinarySearch

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

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

该方法可以将 ThreeSum 算法增长数量级为 $N(N-1)log_2 N$ ,降低为 O( $N^2 logN$ )。

二分查找的复杂度计算:
假设序列里共有n个元素，
第一次，在n个元素内找到目标元素；
第二次，n/2个元素内找到目标元素；
第三次，n/( $2^2$ )个元素内找到目标元素；
······
第k次，n/( $2^k$ )个元素内找到目标元素。

因为 $2^k<=n$ ，所以当且仅当n/( $2^k$ )>=1时，k最大为 $log_2n$ 。

时间复杂度为O( $log_2n$ ).

ThreeSumTwoPointer

数组进行排序，用双指针查找，时间复杂度为 $O(N^2)$

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, h = N - 1, target = -nums[i];// l h 双指针， nums[i]+nums[h]+nums[l]=0,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;
    }
}```