算法与数据结构基础

2020-05-24 1901点热度 0人点赞 0条评论
算法系列参考代码: https://github.com/njZhuMin/algorithm-practice

算法复杂度

评估算法优劣的核心指标一般有以下三个方面:

  • 时间复杂度(流程决定)
  • 额外空间复杂度(流程决定)
  • 常数项时间(实现细节决定)

常数时间操作

我们先来说常数时间操作。如果一个操作的执行时间不以具体样本量为转移,每次执行时间都是固定时间,这样的操作为常数时间的操作。

常见的常数吋囘的操作有:

  • 常见的算术运算(+、-、*、/、%)等
  • 常见的位运算(>> 、>>> 、<< 、|、&、^ 等)
  • 赋值、比较、自増、自减操作等
  • 数组寻址操作

算法流程的总操作数与样本数量之间的关系

  1. 想象该算法流程所处理的数据状况,要按照最差情况来。
  2. 把整个流程彻底拆分为一个个基本动作,保证每个动作都是常数时间的操作。
  3. 如果数据量为 N,看看基本动作的数量和 N 是什么关系。

如何确定算法流程的时间复杂度

当完成了表达式的建立,只要把最高阶项留下即可。低阶项都去掉,高阶项的系数也去掉。
记为:O(忽略掉系数的高阶项)

时间复杂度的意义

有同学可能会有疑问,在估算时间复杂度的时候,我们忽略了所有的低阶项,只剩下了一个最高阶项。如此 “不精确” 的估算有什么意义呢?

估算算法时间复杂度的意义在于:

  • 当我们要处理的样本量很大很大时,我们会发现低阶项是什么不是最重要的。如 N=100 万时,N^310000·N 相比;
  • 每一项的系数是什么,不是最重要的。真正重要的就是最高阶项是什么。

这就是时间复杂度的意义,它是衡量算法流程的复杂程度的一种指标,该指标只与数据量有关,与过程之外的优化无关。

额外空间复杂度

额外空间复杂度是指,在实现算法流程的过程中,你需要开辟一些空间来支持你的算法流程。

  • 作为输入参数的空间,不算额外空间。
  • 作为输出结果的空间,也不算额外空间。

但除此之外,你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。如果你的流程只需要开辟有限几个变量,额外空间复杂度就是 O(1)

问题的最优解

一般面试、比赛、刷题中,解决一个问题的算法流程最优解是指,首先在时间复杂度的指标上,要尽可能的低,先满足了时间复杂度最低这个指标之后,使用最少的空间的算法流程,叫这个问题的最优解。

一般说起最优解都是忽略掉常数项这个因素的,因为这个因素只决定了实现层次的优化和考虑,而和怎么解决整个问题的思想无关。

常数项因素是指,例如加法和乘法都是常数项操作,但是实际上加法的速度就是比乘法快,位运算的速度比乘除快。这样的因素一般不再考虑之内。

认识二分法

二分法最常见的应用场景是在一个有序数组上,开展二分查找。但有序真的是所有问题求解时使用二分的必要条件吗?并不是。
只要能正确构建左右两侧的判定标准,就可以使用二分法。例如以下场景:

  1. 在一个有序数组中, 找某个数是否存在;
  2. 在一个有序数组中, 找>=某个数最左侧的位置;
  3. 在一个有序数组中,找<=某个数最右侧的位置;
  4. 局部极大值问题。
二分查找算法并不是只能用于有序数列。只要能正确构建左右两侧的判定标准,就可以使用二分法。

举例:寻找峰值

LeetCode 162 - Find Peak Element
A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

这道题中的数列是无序的,但是每个数都不相等。我们先看第一个数,如果他比第二个数大([2, 1, ...]),那他本身就是一个局部最大值。否则前两个数一定是增大的趋势(1, 2, ...)。

同理如果最后一个数比倒数第二个数大,那么他也是极一个大值([..., 9, 10])。否则最后两个数字是减小趋势([..., 10, 9])。

那么可以推断,从第二个数到倒数第二个数(index 1 ~ length-1)之间,一定存在至少一个极大值([1, 2, ..., 10, 9])。

我们直接来到中点,如果这个数比前一个小,那么在中点前数字呈现减小趋势([1, 2, ..., 5, 4, ..., 10, 9])。将中点作为新的终点,前半部分一定存在极大值(先增大后减小的趋势)。

否则,如果中点的数比后一个小,那么中点后的数字呈增大趋势([1, 2, ..., 4, 5, ..., 10, 9])。将中点作为新的起点,后半部分一定存在极大值(先增大后减小的趋势)。

如果中间比前一个数大,比后一个数也大,那么这个点本身就是极大值之一。

因此这是一个典型的二分查找场景。实现如下:

public class Q162_BinSearchForPeekElement {
    public int findPeakElement(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] > arr[1]) {
            // 第一个数即是峰值
            return 0;
        }
        if (arr[arr.length - 1] > arr[arr.length - 2]) {
            // 最后一个数即是峰值
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            // 比前一个数小,前一半必然存在峰值,丢弃后一半
            if (arr[mid] < arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] < arr[mid + 1]) {
                // 比后一个数小,后一半必然存在峰值,丢弃前一半
                left = mid + 1;
            } else {
                // 比前数大,比后数大,找到峰值
                return mid;
            }
        }
        return left;
    }
}

SilverLining

也可能是只程序猿

文章评论