算法与数据结构

算法的概念

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法是独立存在的一种解决问题的方法和思想。

对于算法而言，实现的语言并不重要，重要的是思想。

算法可以有不同的语言描述实现版本。

算法的五大特性

1、输入：算法具有0个或多个输入

2、输出：算法至少有1个或多个输出

3、有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以再可接受的时间内完成

4、确定性：算法中的每一步都有确定的含义，不会出现二义性

5、可行性：算法的每一步都是可行的，每一步都能执行有限的次数完成

时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

n表示数据规模 ； O( f(n) )表示运行算法所需要执行的指令数，和f(n)成正比。

时间复杂度的几条基本计算规则：

1、基本操作，即只有常数项，认为其时间复杂度为O（1）

2、顺序结构，时间复杂度按加法计算

3、循环结构，时间复杂度按乘法计算

4、分支结构，时间复杂度取最大值

5、判断一个算法的效率时，往往只需要关注操作数量的最高次项，其他次要项和常数项可以忽略

6、在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度