漫画算法小灰学习算法笔记

 

写在前面的话：

学习算法，需要做的是领悟算法思想、理解算法对内存空间和性能的
影响，以及开动脑筋去寻求解决问题的最佳方案。

 

正文如下：

 

1.1.2 什么是算法

算出1+2+3+4+5+6+7……一直加到10000的结果，算不完不许回家！

(1+10 000)×10 000 ÷ 2 = 50 005 000

所采用的这种等差数列求和的方法，被称为高斯算法。

在数学领域里，算法是用于解决某一类问题的公式和思想。

计算机科学领域的算法，它的本质是一系列程序指令，用于解决特定的

运算和逻辑问题

算法有简单的，也有复杂的。
简单的算法，诸如给出一组整数，找出其中最大的数。

复杂的算法，诸如在多种物品里选择装入背包的物品，使背包里的物品
总价值最大，或找出从一个城市到另一个城市的最短路线

算法有高效的，也有拙劣的

刚才所讲的从1加到10000的故事中，高斯所用的算法显然是更加高效的
算法，它利用等差数列的规律，四两拨千斤，省时省力地求出了最终结
果。
而老师心中所想的算法，按部就班地一个数一个数进行累加，则是一种
低效、笨拙的算法。虽然这种算法也能得到最终结果，但是其计算过程
要低效得多。

在计算机领域，我们同样会遇到各种高效和拙劣的算法。衡量算法好坏
的重要标准有两个。
时间复杂度
空间复杂度

 

1.1.3 什么是数据结构

数据结构是算法的基石。如果把算法
比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的
舞台。

数据结构，对应的英文单词是data structure ，是数据的组织、管理和
存储格式，其使用目的是为了高效地访问和修改数据。
数据结构都有哪些组成方式呢？

1. 线性结构
线性结构是最简单的数据结构，包括数组、链表，以及由它们衍生出来
的栈、队列、哈希表。

2. 树
树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生
出了二叉堆之类的数据结构。

3. 图
图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系

关于算法在不同数据结构上的操作过程，在后续的章节中我们会一一进
行学习。

 

1.2.1 算法的好与坏

时间复杂度和空间复杂度究竟是什么呢？首先，让我们来想象一个场
景。

某一天，小灰和大黄同时加入了同一家公司

一天后，小灰和大黄交付了各自的代码，两人的代码实现的功能差不
多。
大黄的代码运行一次要花100ms ，占用内存5MB 。
小灰的代码运行一次要花100s ，占用内存500MB 。

于是……

在上述场景中，小灰虽然也按照老板的要求实现了功能，但他的代码存
在两个很严重的问题。
1. 运行时间长
运行别人的代码只要100ms，而运行小灰的代码则要100s，使用者肯定
是无法忍受的。
2. 占用空间大
别人的代码只消耗5MB的内存，而小灰的代码却要消耗500MB的内存，
这会给使用者造成很多麻烦。

由此可见，运行时间的长短和占用内存空间的大小，是衡量程序好坏的
重要因素。

 

可是，如果代码都还没有运行，
我怎么能预知代码运行所花的时间呢？

由于受运行环境和输入规模的影响，
代码的绝对执行时间是无法预估的。但我们却可以预估代码的基本
操作执行次数。

 

1.2.2 基本操作执行次数

关于代码的基本操作执行次数：

设T(n)为程序基本操作执行次数的函数（也可以认
为是程序的相对执行时间函数）n为输入规模

场景1 　T(n) = 3n，执行次数3n是线性 的。
1. void eat1(int n){
2. for(int i=0; i<n; i++){;
3. System.out.println("等待1分钟");
4. System.out.println("等待1分钟");
5. System.out.println("吃1cm 面包");
6. }
7. }
场景2 　T(n) = 5logn，执行次数是用对数 计算的。
1. void eat2(int n){
2. for(int i=n; i>1; i/=2){
3. System.out.println("等待1分钟");
4. System.out.println("等待1分钟");
5. System.out.println("等待1分钟");
6. System.out.println("等待1分钟");
7. System.out.println("吃一半面包");
8. }
9. }
场景3 　T(n) = 2，执行次数是常量 。
1. void eat3(int n){
2. System.out.println(" 等待1分钟");
3. System.out.println(" 吃1个鸡腿");
4. }
场景4 　T(n) = 0.5n^2 + 0.5n，执行次数是用多项式 0.5n^2 + 0.5n计算的。
1. void eat4(int n){
2. for(int i=0; i<n; i++){
3. for(int j=0; j<i; j++){
4. System.out.println("等待1分钟");
5. }
6. System.out.println("吃1cm 面包");
7. }
8. }

 

1.2.3 渐进时间复杂度

有了基本操作执行次数的函数T(n)，是否就可以分析和比较代码的运行
时间了呢？还是有一定困难的。
例如算法A的执行次数是T(n)= 100n，算法B的执行次数是T(n)= 5n^2 ，这
两个到底谁的运行时间更长一些呢？这就要看n的取值了

因此，为了解决时间分析的难题，有了渐进时间复杂度（asymptotic
time complexity） 的概念，其官方定义如下。
若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于
零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为
O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。
因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法 。

这个定义好晦涩呀，看不明白。

直白地讲，时间复杂度就是把程序的
相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n^2
、n^3 等。

如何推导出时间复杂度呢？有如下几个原则。
如果运行时间是常数量级，则用常数1表示
只保留时间函数中的最高阶项
如果最高阶项存在，则省去最高阶项前面的系数
让我们回头看看刚才的4个场景。
场景1
T(n) = 3n，
最高阶项为3n，省去系数3，则转化的时间复杂度为：T(n)=O(n) 。

场景2
T(n) = 5logn，
最高阶项为5logn，省去系数5，则转化的时间复杂度为：T(n) =O(logn)
。

场景3
T(n) = 2，
只有常数量级，则转化的时间复杂度为：T(n) =O(1) 。

场景4
T(n) = 0.5n 2 + 0.5n，
最高阶项为0.5n 2 ，省去系数0.5，则转化的时间复杂度为：T(n) =O(n
2  )

这4种时间复杂度究竟谁的程度执行用时更长，谁更节省时间呢？当n的
取值足够大时，不难得出下面的结论：
O(1)<O(logn)<O(n)<O(n^2 )

 

1.2.4 时间复杂度的巨大差异

大黄，我还有一个问题，现在计
算机硬件的性能越来越强了，我们为什么还这么重视时间复杂度
呢？
问得很好，让我们用两个算法来做一
个对比，看一看高效算法和低效算法有多大的差距。

算法A的执行次数是T(n)= 100n，时间复杂度是O(n)。
算法B的执行次数是T(n)= 5n^2 ，时间复杂度是O(n^2 )。

算法A运行在小灰家里的老旧电脑上，算法B运行在某台超级计算机
上，超级计算机的运行速度是老旧电脑的100倍。

那么，随着输入规模n的增长，两种算法谁运行速度更快呢？

从上面的表格可以看出，当n的值很小时，算法A的运行用时要远大于
算法B；当n的值在1000左右时，算法A和算法B的运行时间已经比较接
近；随着n的值越来越大，甚至达到十万、百万时，算法A的优势开始
显现出来，算法B的运行速度则越来越慢，差距越来越明显。
这就是不同时间复杂度带来的差距。

要想学好算法，就必须理解时间复杂
度这个重要的基础概念。有关时间复杂度的知识就介绍到这里，我
们下一节再见！

 

1.3 空间复杂度

1.3.1 什么是空间复杂度

 

在运行一段程序时，我们不仅要执行各种运算指令，同时也会根据需
要，存储一些临时的中间数据  ，以便后续指令可以更方便地继续执
行。

但是，内存空间是有限的，在时间复杂度相同的情况下，算法占用的内
存空间自然是越小越好。如何描述一个算法占用的内存空间的大小呢？
这就用到了算法的另一个重要指标——空间复杂度（space
complexity） 。

和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存
储空间大小的量度，它同样使用了大O表示法。

程序占用空间大小的计算公式记作S(n)=O(f(n)) ，其中n为问题的规模，
f(n)为算法所占存储空间的函数。