数据结构与算法学习之算法基础知识

数据结构与算法的关系

单纯学数据结构应该很快就能学完，但是加上算法就不一样了。数据结构与算法是啥关系呢？不是有说程序设计=数据结构+算法，个人感觉，只谈数据结构不谈算法就是在耍流氓。

算法的重要性

算法实例：求1+2+3+……+100之和第一种方法：

int i , sum = 0 , n ; 100;

for (i = 1; i < = n; i++)

{

sum = sum + í ;

}

printf ( “%s”, sum) ;

第二种方法：

int 1, sum = 0, n = 10.0:

sum = (1 + n) * n I 2;

printf ( " %s"， sum);

显而易见，从代码量上就能知道孰优孰劣了。

算法定义

普遍认可的对算法的定义：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且4事务指令亵示一个或多个操作。

算法的特性

1、输入输出

输入：算法具有零个或多个输入输出：算法至少有一个或多个输出。你写的算法没输出就是在耍流氓。

2、有穷性

指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

3、确定性

算法的每一步骤都具有确定的含义，不会出现二义性。在一定条件下，相同输入只能有唯一对应的输出结果，算法步骤不能有二义性。

4、可行性

算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

算法设计要求

好的算法，应该具有正确性、可读性、健壮性、高效率和低存储量的特征。

1、正确性

算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。正确性有以下四个层次：

2、可读性

算法设计最后也是要用代码表达出来，代码有一个要求就是要便于阅读、理解和交流。一份好的代码肯定首先得是容易阅读理解。算法设计亦要如此，好的算法便于发现错误，调试修改等等。

3、健壮性

当输入数据不合法时，算法也能做出相关处理， 而不是产生异常或莫名其妙的结果。例如：字符串拷贝函数

char *strcpy(char *dest,char *src)

{

char *save_dest = dest;

if(dest == NULL || src == NULL)

{

return;

}

while(*src ！= "\0")

{

*dest = *src;

dest++;

src++;

}

return save_dest ;

}

为了程序的健壮性。得加个判断输入的两个指针是否为空指针，如果为空指针程序就会崩溃了。

4、时间效率高和存储量低

时间效率指的是算法的执行时间。同一个问题，有多种不同解决问题的算法，当然是执行时间越短时间效率越高。同时呢如果算法占用的空间越小那就更好啦，这对于嵌入式设备来说挺重要的。这两个也对应了衡量算法好坏的两个重要指标：时间复杂度和空间复杂度。

算法效率的度量方法1、 事后统计方法

辣鸡。

2、 事前分析估算方法

在计算机程序编制前，依据统计方法对算法进行估算。高级程序语言编写的程序在计算机上运行时所消耗的时 间取决于下列因素:1、算法采用的策略、 方法。

2、 编译产生的代码质量。

3、 问题的输入规模。

4、 机器执行指令的速度。第一个是算法好坏的根本原因。第二个跟编译器有关；第四个是跟计算机性能相关。抛开计算机硬件和编译软件的问题，可知，一个算法的好坏取决于算法的策略、方法以及问题的输入规模。

算法时间复杂度定义

在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的 时间复杂度，也就是算法的时间量度，记作：T（n）=O（f（n））。它表示随问题 规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。

这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。

推导大 O 阶方法：

1、用常数1取代运行时间的所有加法常数。

2 、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。

1、常数阶

int sum = 0，n = 100；/*执行一次*/

sum =（1 + n）*n / 2；/*执行一次*/

printf（"%d"，sum）；/*执行一次*/

共执行三次，但是不是O(3)，根据上面方法1，可知，该算法的时间复杂度是O(1)。

printf（"%d"，sum）；/*执行一次*/

printf（"%d"，sum）；/*执行一次*/

printf（"%d"，sum）；/*执行一次*/

printf（"%d"，sum）；/*执行一次*/

printf（"%d"，sum）；/*执行一次*/

printf（"%d"，sum）；/*执行一次*/

printf（"%d"，sum）；/*执行一次*/

像这样执行7次，时间复杂度一样还是O(1)。

对于分支结构而言，无论是真，还是假，执行的次数都是恒定的，不会随着 n 的变大而发生变化，所以单纯的分支结构(不包含在循环结构中) ，其时间复杂度也是O(1)。

2、线性阶

分析算法的复杂度，关键就是要分析循环结构的运行情况。

int i;

for(i = 0;i < n;i++)

{

printf("%d\r\n",i); /*时间复杂度为0（1）的程序步骤序列*/

}

结构中循环n次，所以这代码时间复杂度是O(n)。

3、对数阶

int num = 1；

while（num < n）

{

num = num * 2；

}

每次乘以2就离n更近一分，则有由2^x=n可得到x=log2^n。由此可知算法时间复杂度是O(logn)。

4、平方阶

int i，j；

for（i = 0；i < n；i++）

{

for（j = 0；j < n；j++）

{

printf("%d %d\r\n",i,j); /*时间复杂度为0（1）的程序步骤序列*/

}

}

内外层都循环n次，总的循环次数便是n的平方。所以算法时间复杂度是O(n^2)。

常见时间复杂度：

常用的时间复杂度所耗费的时间从小到大依次是：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况

数组中查找一个数，可能第一个就是，一次就找到了；也可能是最后一个，可能查了n次才找到。n次这种就是最坏的情况。最坏情况运行时间是一种保证 ，那就是运行时间将不会再坏了 。在应用中，这是一种最重要的需求 ， 通常， 除非特别指定 ， 一般情况下运行时间都是最坏情况的运行时间 。平均运行时间是所有情况中最有意义的，因为它是期望的运行时 间。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f（n）为语句关于n所占存储空间的函数。

学习书籍：《大话数据结构》