数据结构第二章

算法：算法是解决特定问题的步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作。

2.1课堂回顾

? 数据结构的基本概念？数据结构的分类？

2.2数据结构与算法的关系

? 学习数据结构，就会讲到算法？数据结构和算法是什么关系？

? 这个问题怎么回答：算法之于数据结构，就好比祝英台之于梁山伯，朱丽叶之于罗密欧。数据结构如同人的躯体，算法如同人的灵魂。

? 只谈数据结构，我们可以在很短的时间介绍完毕几种重要的数据结构，但是没有算法这个灵魂，学习数据结构如同咀嚼鸡肋。当然，我们这里所说的算法都是简单的算法，只是为了更好地理解数据结构，并不会详细谈及算法的方方面面。我们的课程也是按这样的原则来展开的。

2.3两种算法的比较

打开codeblocks

? 大家已经学过C语言了，接下来我们先看一个例子：求100以内整数的和

void main()
{
    int i,sum = 0, n = 100;

    for(i = 1; i <= n;i++){
        sum = sum + i;
    }

    printf(" %d ",sum);
}

这其实就是一种算法，算法顾名思义：求解具体问题的步骤

另一种算法： 大数学家 高斯

#include <stdio.h>
#include <stdlib.h>

void main()
{
    int i = 1,sum = 0, n = 100;

    sum = (i + n) * 100 / 2;
    printf(" %d ",sum);
}

比较两种算法：

2.4算法定义

? 什么是算法呢？算法是描述解决问题的方法。算法（Algorithm）：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作。没有通用的算法，就像包治百病的药都是传销一样。

? 为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，每一个操作都完成特定的功能，这就是算法。

2.5算法的特性

? 算法的五个基本特性：输入、输出、有穷性、确定性和可行性。

2.5.1 输入输出

? 算法具有0个或者多个输入。

? 算法至少需要一个或者多个输出。

思考： 为什么算法可以有0个输入？
		为什么算法必须要有输出？

2.5.2有穷性

? 有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限的循环，并且每一个步骤在可接受的时间内完成。最典型的一个问题就是--死循环。

2.5.3确定性

? 确定性：算法的每一步都是有确定性的意义，不会出现二义性。算法在一定条件下或者确切的说一次执行中，只有一条执行路径，相同的输入只能有唯一的输出结果。

2.5.4可行性

? 可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。可行性包括两点内容：一、你写的程序必须能够跑起来；二、并且能得到正确的结果。

2.6算法的设计要求

? 算法并不是唯一的，也就是说，同一个问题，可以有多种方法去解决。一个很好地比喻就是条条大路通罗马，但是你一次只能选择走一条。无非就是有远近而已。有个成语叫南辕北辙，还有一个成语叫另辟蹊径。路有远近之分就如同算法也有优劣之分。掌握好的算法，对我们解决问题很有帮助。

? 算法的设计要求：正确性、可读性、健壮性、时间复杂度和空间复杂度（时间效率高和存储量低）

2.6.1正确性

? 正确性：算法的正确性是指算法至少应该具有输入输出和加工处理的无歧义性、能够正确地反应问题的需求，能够得到问题的正确答案。

? 但是算法的正确性通常在用法上有很大的差别，大体分为四个层次：

? 1.算法程序没有语法错误；

? 2.算法程序对于合法的数据输入能够产生满足要求的输出结果；

? 3.算法程序对于非法的数据输入能够产生满足规格的说明结果；

? 4.算法程序对于精心选择的，甚至于刁难的测试数据都有满足要求的输出结果。

? 这四个层次就像修炼体系一样，满足第一条，就正式踏上了数据结构与算法的修炼之路，你就成功开辟了苦海，若你能够满足第二条，那么你便会感觉苦海中心之处露出一点金芒，顷刻之间喷发，是你陷入空灵之境，你便进入了命泉之境；如你能对于一些处心积虑的故意刁难，发出严正警告，便能金光护体，踏上神桥，到达彼岸之境。

? 再简单来说，满足第一条，就解决了温饱问题，满足前两条，就解决了衣食住行，满足前三条，就是基本实现了小康，满足第四条，就实现了全民小康。

2.6.2可读性

? 可读性：算法设计的一切目的是为了便于阅读、理解和交流。站在巨人的肩膀上看的更远，走的更远。

? 写代码的目的不仅仅是为了让计算机执行，还要便于他人阅读，让人理解与交流。也是作为一名合格的程序员的道德要求。

2.6.3健壮性

? 健壮性：一个好的算法还应该对输入数据不合法的情况下做合适的处理。比如输入的年龄必须大于等于0等；当数据输入不合法时，算法也能做出相应处理，而不是产生异常或者莫名的结果。

2.6.4空间复杂度和时间复杂度

? 好的算法还应该具备时间效率高和存储量低的特点。即空间复杂度低和时间复杂度低。

算法效率的度量方法：事后统计法和事前分析估算法
	事后统计法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
	事前分析估算法：在计算机程序编制前，依据统计方法进行估算。
	
经过分析，一个用高级语言编写的程序在计算机上运行所消耗的时间取决于下列因素：1.算法采用的策略、方法。（算法好坏的根本）2.编译产生的代码质量。（需要软件支持）3.问题的输入规模。4.机器执行指令的速度。（需要硬件支持）

测定运行时间最可靠的方法就是计算运行时间有小号的基本操作的执行次数。运行时间和这个计数成正比。我们不关心编写程序所用的设计语言是什么，也不关心这些程序跑在什么样的机器上，我们只关心它所实现的算法。这样，不计那些循环索引的递增和循环种植条件、声明变量、打印结果等操作，最终，在分析程序的运行时间时，最重要的是把程序看成是独立与设计语言的算法或一系列操作。

2.7算法的时间复杂度

定义： 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。

2.7.1 推导大O阶方法（数据结构就是一场游戏，这就是你的游戏攻略）

推导大O阶：
1. 用常数1代替运行时间中所有加法常数；
2. 在修改后的运行次数中，只保留最高阶；
3.如果最高阶项存在且不是1，则取出与这个项相乘的常数。
得到的结果就是大O阶

常数阶、线性阶、对数阶、平方阶

常见的时间复杂度

2.8最坏情况与平均情况

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏的情况的运行时间。

平均运行时间是最有意义的，因为他是期望的运行时间。

一般在没有特殊说明的情况下，都是指最坏时间复杂度。

数据结构第二章