算法图解 第一章

1 算法简介

1.2 二分查找

1.2.1二分查找实现

/**
 * 递归方式
 *
 * @param target 目标值
 * @param start  开始索引
 * @param end    结束索引
 * @param arr    数组
 * @return 目标值索引
 */

public static int findNumber(int target, int start, int end, int[] arr) {
    if (start > end) {
        return -1;
    }
    int mid = (start + end) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return findNumber(target, mid + 1, end, arr);
    } else {
        return findNumber(target, start, mid - 1, arr);
    }
}


/**
 * 非递归方式
 *
 * @param target 目标值
 * @param arr    数组
 * @return 目标值索引
 */
public static int findNumber(int target, int[] arr) {
    int start = 0;
    int end = arr.length - 1;
    int mid = (start + end) / 2;
    while (start <= end) {
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
        mid = (start + end) / 2;
    }
    return -1;
}

1.3大O表示法

1.3.1 算法的运行时间以不同的速度增加

1.3.3 大O 表示法指出了最糟情况下的运行时间

1.3.4 一些常见的大O 运行时间

下面按从快到慢的顺序常会遇到的5种大O运行时间：

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，这样的算法包括第4章将介绍的快速排序———— 一种速度较快的排序算法。
• O(n2)，这样的算法包括第2章将介绍的选择排序———— 一种速度较慢的排序算法。
• O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案———— 一种非常慢的算法。

 算法的速度指的并非时间，而是操作数的增速。

 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

 算法的运行时间用大O表示法表示。

 O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

1.4小节

• 二分查找的速度比简单查找快得多。
• O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
• 算法运行时间并不以秒为单位。
• 算法运行时间是从其增速的角度度量的。
• 算法运行时间用大O表示法表示。