1时间复杂度分析.md

1 时间复杂度分析

下面代码实现了删除排序数组中的重复项

    //删除排序数组中的重复项
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        int len = 1;
        int cur = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[cur] == nums[i]) {
                continue;
            }
            nums[++cur] = nums[i];
            len++;
        }
        return len;
    }

分析如下

• 开头2个边界状况处理的指令都是O(1)的操作
• 主体是一个单层for循环，循环内部的指令都是O(1)的操作，所以循环体的时间复杂度为O(n)
• 函数整体时间复杂度=O(1)+O(n)，去掉低阶项，最终时间复杂度为O(n)
• 只使用了固定几个辅助变量，所以空间复杂度为O(1)

2 时间复杂度学习体会

时间复杂度是衡量程序运行效率的指标，反应的是程序运行时间随着处理数据量的变化而变化的一个趋势

常见时间复杂度从好到坏的排序是：O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(n^3)>O(n!)>O(2^n)

2.1 时间复杂度的计算方法

• 普通指令一般为O(1)
• 循环n次的单层循环为O(n)
• 递归的基本时间复杂度为O(n)，如果函数体一次调用了k个递归函数，则为O(k^n)，递归是分治思想的体现，分治法的时间复杂度可由主定理公式算出

2.2 实践

当碰到问题时，我们应该列出问题的所有解决方案，然后算出每种方案的时间复杂度，比较得出最优的解法 想达到快速比较的能力，需要不断的练习，优化算法就是这个过程的不断迭代

3 主定理的使用

视频中没有讲主定理的通用使用方式，即各个参数的意义和代入方法，网上对于公式的说法有两种，下面是容易记的一种。

规模为n的问题通过分治，得到a个规模为n/b的问题，每次递归带来的额外计算为c(n^d) T(n) <= aT(n/b)+c(n^d)

当a = b^d时，T(n) = O(n^d log(n)) 当a < b^d时，T(n) = O(n^d) 当a > b^d时，T(n) = O(n^logb(a))