《图解算法》第1章 算法简介

第1章 算法简介

引言

算法是一组完成任务的指令。任何代码片段都可视为算法

性能

你无需自己动手编写每种算法的代码！但如果你不明白其优缺点，这些实现将毫无用处

问题解决技巧

• 你将学习至今都没有掌握的问题解决技巧

1. 如果你喜欢开发电子游戏，可使用图算法编写跟踪用户的AI系统
2. 你将学习使用K最近令算法编写推荐系统
3. 有些问题在有限的时间内是不可解的！书中讨论NP完全问题的部分将告诉你，如何识别这样的问题以及如何设计找到近似答案的算法

阅读本书，需要具备基本的代数知识。具体说，给定函数f(x)=x × 2，f(5)的值 是多少呢？如果你的答案为10，那就够了

二分查找

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素饮食在列表中，二分查找返回其位置；否则返回null

更佳的查找方式

• 一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步

对数：你可能不记得什么是对数了，但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个：10×10=100。因此，log10100=2。对数运算是幂运算的逆运算。

对数是幂运算的逆运算 本书使用大O表示法讨论运行时间时，log指的都是log2。使用简单查找法查找元素时，在最糟糕情况下需要查看每个元素。因此，如果列表包含8个数字，你最多需要检查8个数字。而使用二分查找时，最多需要检查log n个元素。如果列表包含8个元素，你最多需要检查3个元素，因为log8=3（23=8）。如果列表包含1024个元素，你最多需要检查10个元素，因为log 1024=10（210=1024） 说明：仅当列表是有序的时候，二分查找才管用。例如，电话簿中的名字是按字母顺序排列的，因此可以使用二分查找来查找名字

/**
 * 二分查找法，时间复杂度：log2n
 */
function binary_search($list, $item) {
    // 1. 因为查找下标，所以从0到99
    $low = 0;
    $high = count($list) - 1;
    while ($low <= $high) { // 2. 只要范围没有缩小到只包含一个元素
        $mid = floor(($high + $low) / 2); // 3. 检查中间位置，向下取整
        $guess = $list[ $mid ];
        echo "当前猜的数：{$guess}，low[{$low}]，high[{$high}]\n";
        if ($item == $guess) { // 4. 找到查找元素
            return $guess;
        } elseif ($guess < $item) { // 5. 猜的字小了
            $low = $mid + 1;
        } else {
            $high = $mid - 1; // 6. 猜的数大了
        }
    }
}

$list = range(1, 100);
$item = mt_rand(1, 100);
echo "要猜的数：{$item}\n";
$result = binary_search($list, $item);
echo "猜中的数：{$result}";

运行时间

线性时间（linear time）：最多需要猜测的次数与列表长度相同 二分查找的运行时间为对数时间（或log时间）

大O表示法

你经常要使用别人编写的算法，在这种情况下，知道这些算法的速度大有裨益

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

仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地

大O表示法让你能够比较操作数，它指出了算法运行时间的增速 大O表示法像下面这样，它指出了算法需要执行的操作数

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

除最糟糕情况下的运行时间外，还应考虑平均情况的运行时间，这很重要

一些常见的大O运行时间

• 从快到慢的顺序列出了经常会遇到的5种大O运行时间

1. O（log n），也对对数时间，这样的算法包括二分查找
2. O（n），也叫线性时间，这样的算法包括简单查找
3. O（n*log n），这样的算法包括快速排序（速度较快）
4. O（n2），这样的算法包括选择排序（速度较慢）
5. O（n!），这样的算法包括旅行商问题的解决方案（一种非常慢的算法）

• 当前我们获得的主要启示如下

1. 算法的速度指的并非时间，而是操作数的增速
2. 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加
3. 算法的运行时间用大O表示法表示
4. O（log n）比O（n）快，当需要搜索的元素越多时，前者比后者快得越多

旅行商

有一位旅行商。这位旅行商要前往5个城市，同时要确保旅程最短。对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。5个城市有120种不同的排列方式 n!（n的阶乘）