数据结构概论

1946年首台计算机ENIAC问世。
计算机软件相对硬件发展缓慢。软件的核心是算法,算法是加工数据的过程。
数据的存储结构是逻辑结构用计算机语言的实现。本课程数据结构主要是讨论存储结构,并且我们只在高级语言的层次上讨论存储结构。

时间复杂度

时间复杂度是省去了系数的,平均查找长度则是有系数的。
n!的算法的时间复杂度是O(n)。
{i=s=0;while(s<=n){i++;s+=i;}}时间复杂度O(n1/2)

一个算法应该具有以下五个重要的特征:
### 有穷性(Finiteness)算法的有穷性是指算法必须能在执行有限个步骤之后终止;
### 确切性(Definiteness)算法的每一步骤必须有确切的定义;
### 输入项(Input)一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;
### 输出项(Output)一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
### 可行性(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性)。

发表评论