Essential Algorithms读书笔记(1)

Essential Algorithms读书笔记
2.7k 詞

目录

了解算法

为了充分使用算法，我们必须做的不仅仅是简单地遵循其步骤，还需要了解以下内容：

  • 算法行为：它是否找到了最好的解决方案，或者只是找到了一个好的解决方案？ 是否存在多个最佳解决方案？ 是否有理由选择一个"最佳"解决方案而不是其他解决方案？
  • 运算速度：快？还是慢？还是取决于你输入的内容？
  • 内存需求：这个算法需要多少内存？
  • 技术含量：我们可以多次用同样技术来解决类似的问题吗？

本书涵盖了所有以上主题。然而，它并不试图像数学一样那么精确去涵盖每个算法的每个细节。它使用直观的方法来解释算法及其性能，但没有严格详细地分析性能。尽管这种证明过程可能很有趣，但它也可能令人困惑，提供了大多数程序员不需要的详细程度。毕竟，算法主要是为需要完成工作的程序员而写的。

无序列表的第一项体现了算法不唯一，但是可能有最优解

算法和数据结构与伪代码

数据结构

算法通常与数据结构密切相关，这一点会在以后讲到。

伪代码

下面是伪代码，为了使描述的算法尽可能有用且易于我们理解，它们首先用直观的英语术语进行描述。 从这个高级解释中，我们应该能够用大多数编程语言实现该算法。

故，伪代码是很像编程语言的文本，但并不是真正的编程语言。伪代码可以帮助你理解算法，用来表示程序执行过程，而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。伪代码用来表达程序员开始编码前的想法。

下面是一个中文伪代码的例子，求的是两个整数的最大公约数（Greatest Common Divisor, GCD）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 求两个整数的最大公约数
// GCD(a, b) = GCD (b, a Mod b).
//while 如果始终符合......
整数: Gcd(整数: a, 整数: b)
    如果始终符合 (b 不等于 0) 则一直进行下一级缩进
// 计算余项.
      整数: 余数 = a 取模 b
// 计算 GCD(b, 余数).
      a = b
      b = 余数
    结束 缩进
// GCD(a, 0) is a.
    返回 a
结束 Gcd

若是英文版，则是这样的： 英文版伪代码

在此章节以后，我们的伪代码都使用英语来完成。

取模运算符

取模，其实是取余数，英文常缩写为Mod（modulo），例如，13 Mod 4 =1

我们现在看这个伪代码，若你有一定的编程基础，你可能看懂了，这个伪代码以注释开头。注释以字符 // 开始，一直延伸到行尾。

第一行代码是算法的声明。该算法称为 Gcd，返回整数结果。它有两个名为 a 和 b 的参数，这两个参数都是整数。

执行任务（可选地返回结果）的代码块被不同地称为例程、子例程、方法、过程、子过程或函数(不过以函数为名称叫的多，下面遇到这些可以用来解决问题的代码块不加声明一律说成函数)

英文伪代码讲解

声明后的代码缩进以表明它是方法的一部分。方法主体中的第一行开始一个 While 循环。只要 While 语句中的条件保持为 true，就会执行 While 语句下面缩进的代码。

While 循环以 End While 语句结束。该语句并不是绝对必要的，因为缩进显示了循环结束的位置，但它提醒了哪种语句块正在结束。

该方法在 Return 语句处退出。该算法返回一个值，因此，这个 Return 语句指示该算法应返回哪个值。如果算法不返回任何值，例如其目的是排列值或构建数据结构，则 Return 语句后面不会跟有返回值，或者该方法可能没有 Return 语句。换句话讲，如果只需要让函数执行某个功能，则不需要返回值，需要返回值的，是要对传入数据进行加工的。

那么，接下来我们将伪代码翻译成常用代码，下面举两个例子：

伪代码:

For i = 100 To 0 Step -5
    // Do something...
Next i

C#代码

1
2
3
4
for (int i = 100; i >= 0; i -= 5)
{
    // Do something...
}

Python代码

1
2
for i in range(100, -1, -5):
  # Do something...

本书中使用的伪代码使用了 If-Then-Else 语句、Case 语句以及其他需要的语句。根据我们对实际编程语言的了解，我们应该熟悉这些内容。 代码需要的任何其他内容均以英语拼写。

算法特征

一个好的算法必须具备三个特点：正确性、持续性、高效性。

显然，如果一个算法不能解决它设计时要解决的问题，那么它就没有多大用处。如果它不能得出正确的答案，那么使用它就没有什么意义。

一些算法仅在某些时候产生正确的答案，但它仍然有用。例如，偶然得出算法能够可以有一定可能地为你提供一些信息。在这种情况下，我们可以多次重新运行算法，以增加对答案的信心。例如第 2 章"数值算法"中描述的费马素性检验就是这种算法。

如果算法没有可持续性，那么这对程序来说无疑是危险的，例如，你今天成功解决了一个东西，程序运行得没问题，但是明天你发现这不能用了，那可以等着跑路了（）

所以算法越简洁，直观，并且"优雅"，可以让你思路清晰，少些犯错，我们可以确信它会产生正确的结果，如果没有，我们可以快速修复它。

如果算法错综复杂、令人困惑且令人费解，那么在实现它时可能会遇到很多麻烦，并且如果出现错误，将更难以修复它。如果很难理解，你怎么知道它是否产生了正确的结果？

这并不意味着不值得研究令人困惑和困难的算法。 即使在实现算法时遇到困难，也可以在尝试中学到很多东西。随着时间的推移，你的算法直觉和技能将会增强，因此你曾经认为令人困惑的算法将看起来更容易处理。但是，我们必须始终彻底测试所有算法，以确保它们产生正确的结果。

Big O Notation（大O表示法）

当一个问题很复杂，解决规模很大的时候，可以使用大O表示法来设计一个函数，他们表示算法的最坏情况性能与问题规模之间的关系。（这有时称为程序的渐近性能。）该函数写在大写字母 O 后面的括号内。

例如，O(\(N^2\)) 意味着算法的运行时间（或内存使用量或您正在测量的任何内容）随着输入数量 N 的平方而增加。如果将输入数量加倍，则运行时间大约会增加 4 倍。同样，如果将输入数量增加两倍，则运行时间会增加 9 倍。

大 O 表示法有五个基本规则。

  1. 如果算法对数学函数 \(f\) 执行特定的步骤顺序 \(f(N)\) 次，则需要 \(O(f(N))\) 个步骤。

  2. 如果一个算法对数学函数 \(f_1\) 执行特定的步骤顺序 \(f_1(N)\) 次，再对数学函数 \(f_2\) 执行特定的步骤顺序 \(f_2(N)\) 次，如此类推，整个算法的步骤为\(O(\sum\limits_{i=1}^{n}f_n(N) )\)

  3. 如果算法需要 \(O(f_1(N) + f_2(N))\) 时间，并且对于较大的 \(N\)，函数 \(f_1(N)\) 大于 \(f_2(N)\)，则该算法的性能可以简化为 \(O(f_1(N))\)。

  4. 如果算法执行需要 \(O(f_1(N))\) 步骤的操作，并且对于该操作中的每个步骤，它执行另一个 \(O(f_2(N))\) 步骤，则该算法的总性能为 $O(_{i=1}^{n}f_n(N)) $。

  5. 忽略常量倍数。 如果 \(C\) 是常数，则 \(O(C\times f(N))\) 与 \(O(f(N))\) 相同，\(O(f(C\times N))\) 与 \(O(f(N))\) 相同。

类似于加法计数原理和乘法计数原理，加法计数原理的本质是分类计算，而乘法计数原理的本质是分布计算（来自高中教材选择性必修三人教A版）

下面是对五个基本规则的解释：

规则1

如果算法对数学函数 \(f\) 执行特定的步骤序列 \(f(N)\) 次，则需要 \(O(f(N))\) 个步骤。

下面是伪代码：本质是一个一个比较，然后去掉小的那一个

Integer: FindLargest(Integer: array[])
  Integer: largest = array[0]
  For i = 1 To <largest index>
    If (array[i] > largest) Then largest = array[i]
  Next i
  Return largest
End FindLargest

在一个数组中，我们把所有的\(N\)个数字都比了个遍，所以需要\(O(f(N))\) 个步骤。

规则2

如果一个算法对数学函数 \(f_1\) 执行特定的步骤顺序 \(f_1(N)\) 次，再对数学函数 \(f_2\) 执行特定的步骤顺序 \(f_2(N)\) 次，如此类推，整个算法的步骤为 \(O(\sum\limits_{i=1}^{n}f_n(N) )\)

我们进行特殊化，分为两类，一个是\(f(N)\)，还有一类是\(g(N)\)

如果我们再次查看上一节中显示的 FindLargest 算法，我们会发现有几个步骤实际上并不在循环内。 以下伪代码显示了相同的步骤，其运行时顺序显示在注释中的右侧：

Integer: FindLargest(Integer: array[])
  Integer: largest = array[0]         // O(1)
  For i = 1 To <largest index>        // O(N)
    If (array[i] > largest) Then largest = array[i]
  Next i
  Return largest            // O(1)
End FindLargest

如上面的伪代码所示，该算法在进入循环之前执行一个设置步骤，然后在完成循环后再执行一个步骤。这两个步骤的性能都是 \(O(1)\)（它们每个都只是一个步骤），因此算法的总运行时间实际上是 \(O(1+N+1)\) 我们可以使用普通代数来组合项，将其重写为 \(O(2+N)\)。


本文地址： https://wingsfrontier.top/posts/48591.html
版权声明：转载请注明出处！