Skip to content

Commit bf25758

Browse files
facertfacert
committed
init
1 parent b957db1 commit bf25758

317 files changed

Lines changed: 4017 additions & 16 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎.gitignore‎

Lines changed: 2 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,2 @@
1-
# Node rules:
2-
## Grunt intermediate storage (http://gruntjs.com/creating-plugins#storing-task-files)
3-
.grunt
4-
5-
## Dependency directory
6-
## Commenting this out is preferred by some people, see
7-
## https://docs.npmjs.com/misc/faq#should-i-check-my-node_modules-folder-into-git
8-
node_modules
9-
10-
# Book build output
11-
_book
12-
13-
# eBook build output
14-
*.epub
15-
*.mobi
16-
*.pdf
1+
_book/*
2+
assets/*

‎1.介绍/1.1.目标/README.md‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
2+
## 1.1.目标
3+
4+
* 回顾计算机科学的思想, 提高编程和解决问题的 能力。
5+
* 理解抽象化以及它在解决问题过程中发挥的作用
6+
* 理解和实现抽象数据类型的概念
7+
* 回顾 Python 编程语言
8+
9+

‎1.介绍/1.2.快速开始/README.md‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
## 1.2.快速开始
2+
从第一台通过接入网线和交换机来传递人的指令的计算机开始，我们编程思考的方式发生了许多变化。与社会的许多方面一样，计算技术的变化为计算机科学家提供了越来越多的工具和平台来实践他们的工艺。计算机的快速发展诸如更快的处理器，高速网络和大的存储器容量已经让计算机科学家陷入高度复杂螺旋中。在所有这些快速演变中，一些基本原则保持不变。计算机科学关注用计算机来解决问题。
3+
4+
5+
毫无疑问你花了相当多的时间学习解决问题的基础知识，以此希望有足够的能力把问题弄清楚并想出解决方案。你还发现编写代码通常很困难。问题的复杂性和解决方案的相应复杂性往往会掩盖与解决问题过程相关的基本思想。
6+
7+
本章着重介绍了其他两个重要的部分。首先回顾了计算机科学与算法和研究数据结构所必须适应的框架，特别是我们需要研究这些主题的原因，以及如何理解这些主题有助于我们更好的解决问题。第二，我们回顾 Python 编程语言。虽然我们不提供详尽的参考，我们将在其余章节中给出基本数据结构的示例和解释。
8+
9+

‎1.介绍/1.3.什么是计算机科学/README.md‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
## 1.3.什么是计算机科学
2+
计算机科学往往难以定义。这可能是由于在名称中不幸使用了“电脑”一词。正如你可能知道的，计算机科学不仅仅是计算机的研究。虽然计算机作为一个工具在学科中发挥重要的支持作用，但它们只是工具。
3+
4+
计算机科学是对问题，解决问题以及解决问题过程中产生的解决方案的研究。给定一个问题，计算机科学家的目标是开发一个算法，一系列的指令列表，用于解决可能出现的问题的任何实例。算法遵循它有限的过程就可以解决问题。
5+
6+
计算机科学可以被认为是对算法的研究。但是，我们必须谨慎地包括一些事实，即一些问题可能没有解决方案。虽然证明这种说法正确性超出了本文的范围，但一些问题不能解决的事实对于那些研究计算机科学的人是很重要的。所以我们可以这么定义计算机科学，是研究能被解决的问题的方案和不能被解决问题的科学。
7+
8+
通常我们会说这个问题是可计算的，当在描述问题和解决方案时。如果存在一个算法解决这个问题，那么问题是可计算的。计算机科学的另一个定义是说，计算机科学是研究那些可计算和不可计算的问题，研究是不是存在一种算法来解决它。你会注意到，“电脑”一词根本没有出现。解决方案是独立于机器而言的。
9+
10+
计算机科学，因为它涉及问题解决过程本身，也是抽象的研究。抽象使我们能够以分离所谓的逻辑和物理角度的方式来观察问题和解决方案。基本思想跟我们常见的例子一样。
11+
12+
假设你可能已经开车上学或上班。作为司机，汽车的用户。你为了让汽车载你到目的地，你会和汽车有些互动。进入汽车，插入钥匙，点火，换挡，制动，加速和转向。从抽象的角度，我们可以说你所看到的是汽车的逻辑视角。你正在使用汽车设计师提供的功能，将你从一个地方运输到另一个位置。这些功能有时也被称为接口。
13+
14+
15+
另一方面，修理汽车的技工有一个截然不同的视角。他不仅知道如何开车，还必须知道所有必要的细节，使我们认为理所当然的功能运行起来。他需要了解发动机是如何工作的，变速箱如何变速，温度是如何控制的等等。这被称为物理视角，细节发生在“引擎盖下”。
16+
17+
当我们使用电脑时也会发生同样的情况。大多数人使用计算机写文档，发送和接收电子邮件，上网冲浪，播放音乐，存储图像和玩游戏，而不知道让这些应用程序工作的细节。他们从逻辑或用户角度看计算机。计算机科学家，程序员，技术支持人员和系统管理员看计算机的角度截然不同。他们必须知道操作系统如何工作的细节，如何配置网络协议，以及如何编写控制功能的各种脚本。他们必须能够控制底层的细节。
18+
19+
这两个示例的共同点是用户态的抽象，有时也称为客户端，不需要知道细节，只要用户知道接口的工作方式。这个接口是用户与底层沟通的方式。作为抽象的另一个例子，Python 数学模块。一旦我们导入模块，我们可以执行计算
20+
21+
```` python
22+
>>> import math
23+
>>> math.sqrt(16)
24+
4.0
25+
>>>
26+
````
27+
28+
这是一个程序抽象的例子。我们不一定知道如何计算平方根，但我们知道函数是什么以及如何使用它。如果我们正确地执行导入，我们可以假设该函数将为我们提供正确的结果。我们知道有人实现了平方根问题的解决方案，但我们只需要知道如何使用它。这有时被称为“黑盒子”视图。我们简单地描述下接口：函数的名称，需要什么（参数），以及将返回什么。细节隐藏在里面（见图1）。
29+
![blackbox](assets/blackbox.png)
30+
（图1）
31+
32+
33+
34+
35+
36+
37+
38+
39+
40+
41+
42+
43+
44+
45+
46+
47+
48+

‎1.介绍/1.3.什么是计算机科学/assets/blackbox.png‎

6.95 KB
Loading

‎1.介绍/1.4.什么是编程/README.md‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
## 1.4.什么是编程
2+
**编程**是将算法编码为符号，编程语言的过程，以使得其可以由计算机执行。虽然有许多编程语言和不同类型的计算机存在，第一步是需要有解决方案。没有算法就没有程序。
3+
4+
计算机科学不是研究编程。然而，编程是计算机科学家的一个重要能力。编程通常是我们为解决方案创建的表现形式。因此，这种语言表现形式和创造它的过程成为该学科的基本部分。
5+
6+
算法描述了依据问题实例数据所产生的解决方案和产生预期结果所需的一套步骤。编程语言必须提供一种表示方法来表示过程和数据。为此，它提供了控制结构和数据类型。
7+
8+
控制结构允许以方便而明确的方式表示算法步骤。至少，算法需要执行顺序处理，决策选择和重复控制迭代。只要语言提供这些基本语句，它就可以用于算法表示。
9+
10+
计算机中的所有数据项都以二进制形式表示。为了赋给这些字符串含义，我们需要有数据类型。数据类型提供了对这个二进制数据的解释，以便我们能够根据解决的问题思考数据。这些底层的内置数据类型（有时称为原始数据类型）为算法开发提供了基础。
11+
12+
例如，大多数编程语言为整数提供数据类型。内存中的二进制数据可以解释为整数，并且能给予一个我们通常与整数（例如 23,654 和 -19）相关联的含义。此外，数据类型还提供数据项参与的操作的描述。对于整数，诸如加法，减法和乘法的操作是常见的。我们期望数值类型的数据可以参与这些算术运算。通常我们遇到的困难是问题及其解决方案非常复杂。这些简单的，语言提供的结构和数据类型虽然足以表示复杂的解决方案，但通常在我们处理问题的过程中处于不利地位。我们需要一些方法控制这种复杂性，并能给我们提供更好的解决方案。
13+
14+
15+
16+
17+
18+
19+
20+
21+
22+
23+
24+
25+
26+
27+
28+
29+
30+
31+
32+

‎1.介绍/README.md‎

Whitespace-only changes.

‎2.算法分析/2.1.目标/README.md‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
## 2.1.目标
2+
3+
* 理解算法的重要性
4+
* 使用 大*O* 符号表示执行时间
5+
* 理解 Python 列表和字典的大*O*执行时间
6+
* 理解 Python 数据的实现是如何影响算法分析的。
7+
* 了解如何对 Python 程序做简单的基准测试。
8+
9+
10+
11+

‎2.算法分析/2.2.什么是算法分析/README.md‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
## 2.2.什么是算法分析
2+
一些普遍的现象是，刚接触计算机科学的同学会将自己的程序和其他的相比较。你可能还注意到，计算机程序看起来很相似，尤其是简单的程序。经常出现一个有趣的问题。当两个程序解决同样的问题，但看起来不同，哪一个更好呢？为了回答这个问题，我们需要记住，程序和程序代表的底层算法之间有一个重要的区别。正如我们在第 1 章中所说，一个算法是一个通用的，解决问题的指令列表。它是用于解决问题的任何实例的方法，给定特定输入，产生期望的结果。另一方面，程序是已经被编码成某种编程语言的算法。根据所使用的编程器和编程语言，可能存在用于相同算法的许多程序。要进一步探讨这种差异，请参考 ActiveCode 1 中显示的函数。这个函数解决了一个熟悉的问题，计算前 n 个整数的和。该算法使用初始化为 0 的累加器变量。然后迭代 n 个整数，将每个添加到累加器。
3+
4+
```` python
5+
def sumOfN(n):
6+
theSum = 0
7+
for i in range(1,n+1):
8+
theSum = theSum + i
9+
10+
return theSum
11+
12+
print(sumOfN(10))
13+
14+
````
15+
*ActiveCode 1*
16+
17+
现在看看 ActiveCode 2 中的函数。乍一看，它可能很奇怪，但进一步的观察，你可以看到，这个功能本质上和前面的程序做同样的事情。不直观的原因在于编码习惯不好。我们没有使用良好的标识符名称来提升可读性，我们在迭代步骤中使用了一个额外的赋值语句，这并不是真正必要的。
18+
19+
```` python
20+
def foo(tom):
21+
fred = 0
22+
for bill in range(1,tom+1):
23+
barney = bill
24+
fred = fred + barney
25+
26+
return fred
27+
28+
print(foo(10))
29+
30+
````
31+
*ActiveCode 2*
32+
33+
先前我们提出一个问题是哪个函数更好，答案取决于你的标准。如果你关注可读性，函数 sumOfN 肯定比 foo 好。事实上，你可能已经在你介绍编程的课程中看到过很多例子，他们的目标之一就是帮助你编写易于阅读和理解的程序。在本课程中，我们对如何表示算法感兴趣（当然我们希望你继续努力编写可读的，易于理解的代码）。
34+
35+
算法分析涉及基于每个算法使用的计算资源量来比较算法。我们比较两个算法，说一个比另一个算法好的原因在于它在使用资源方面更有效率，或者仅仅使用的资源更少。从这个角度来看，上面两个函数看起来很相似。它们都使用基本相同的算法来求解问题。在这点上，更重要的是我们如何考虑真正意义上的计算资源。有两个方法，一种是考虑算法所需的空间或者内存。所需的空间通常由问题本身决定。但是，算法会有一些特殊的空间需求，我们可以细细观察解释这些变动。
36+
37+
作为空间需求的一种替代方法，我们可以基于时间来分析算法。这种度量有时被称为算法的‘执行时间’或’运行时间‘。我们可以通过基准分析来测量函数 SumOfN 的执行时间。这意味着我们将记录程序计算所需的实际时间。在 Python 中，我们可以通过记录相对于系统的开始时间和结束时间来对函数进行基准测试。在时间模块中有一个时间函数，它将返回系统时钟时间（以秒为单位）。通过在开始和结束的时候调用时间函数，然后计算差异，就可以得到一个精确地秒数（大多数情况下）。
38+
39+
#### Listing 1
40+
41+
```` python
42+
import time
43+
44+
def sumOfN2(n):
45+
start = time.time()
46+
47+
theSum = 0
48+
for i in range(1,n+1):
49+
theSum = theSum + i
50+
51+
end = time.time()
52+
53+
return theSum,end-start
54+
````
55+
56+
Listing 1 嵌入了时间函数，函数返回一个包含结果和消耗时间的数组。如果我们 执行这个函数 5 次，每次计算前 10,000 个整数的和，将得到一下结果：
57+
58+
````
59+
>>>for i in range(5):
60+
print("Sum is %d required %10.7f seconds"%sumOfN(10000))
61+
Sum is 50005000 required 0.0018950 seconds
62+
Sum is 50005000 required 0.0018620 seconds
63+
Sum is 50005000 required 0.0019171 seconds
64+
Sum is 50005000 required 0.0019162 seconds
65+
Sum is 50005000 required 0.0019360 seconds
66+
````
67+
68+
我们发现时间是相当一致的，它执行该代码平均需要0.0019秒。如果我们运行计算前 100,000个 整数的函数呢？
69+
70+
````
71+
>>>for i in range(5):
72+
print("Sum is %d required %10.7f seconds"%sumOfN(100000))
73+
Sum is 5000050000 required 0.0199420 seconds
74+
Sum is 5000050000 required 0.0180972 seconds
75+
Sum is 5000050000 required 0.0194821 seconds
76+
Sum is 5000050000 required 0.0178988 seconds
77+
Sum is 5000050000 required 0.0188949 seconds
78+
>>>
79+
````
80+
81+
再次的，尽管时间更长，每次运行所需的时间是非常一致的，平均大约多10倍。 对于 n 等于 1,000,000，我们得到：
82+
83+
````
84+
>>>for i in range(5):
85+
print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
86+
Sum is 500000500000 required 0.1948988 seconds
87+
Sum is 500000500000 required 0.1850290 seconds
88+
Sum is 500000500000 required 0.1809771 seconds
89+
Sum is 500000500000 required 0.1729250 seconds
90+
Sum is 500000500000 required 0.1646299 seconds
91+
>>>
92+
````
93+
在这种情况下，平均值也大约是前一次的10倍。现在考虑ActiveCode 3，它显示了求解求和问题的不同方法
94+
![求和](assets/%E6%B1%82%E5%92%8C.png)
95+
96+
97+
```` python
98+
def sumOfN3(n):
99+
return (n*(n+1))/2
100+
101+
print(sumOfN3(10))
102+
````
103+
*ActiveCode 3*
104+
105+
如果我们对 sumOfN3 做同样的基准测试，使用 5 个不同的 n(10,000, 100,000, 1,000,000, 100,000,000), 我们得到如下结果
106+
107+
```` python
108+
Sum is 50005000 required 0.00000095 seconds
109+
Sum is 5000050000 required 0.00000191 seconds
110+
Sum is 500000500000 required 0.00000095 seconds
111+
Sum is 50000005000000 required 0.00000095 seconds
112+
Sum is 5000000050000000 required 0.00000119 seconds
113+
````
114+
115+
有两点关注下，首先上面记录的时间比上面任何例子都短， 另外他们的时间和 n 无关， 看来 sumOfN3 几乎不受 n 的影响。
116+
117+
但是这个基准测试告诉我们什么？我们可以直观的看到用迭代的方案在做更多的工作，因为一些步骤重复。这可能是它需要更长时间的原因。此外，迭代所需时间随着 n 递增。还有个问题，如果我们在不同计算机上或者使用不用的编程语言运行这个函数，我们也可能得到不同的结果。如果用老计算机，可能需要更长时间才能执行完 sumOfN3。
118+
119+
120+
我们需要一个更好的方法来表征这些算法的执行时间。基准测试计算的是执行的实际时间。它并不真正提供给我们一个有用的测量，因为它取决于特定的机器，程序，时间，编译器和编程语言。 相反，我们希望具有独立于所使用的程序或计算机的特性。不过基准度量将有助于单独判断算法，并且可以用于在方案之间比较算法。
121+
122+
123+
124+
125+

‎2.算法分析/2.2.什么是算法分析/assets/求和.png‎

7.6 KB
Loading

0 commit comments

Comments
 (0)