[数据结构与算法] 数据结构---算法

一、抽象数据类型=逻辑结构+抽象运算

在这里插入图片描述

ADT <抽象数据类型名>
{
数据对象：<数据对象的定义>
数据关系： <数据关系的定义>
基本操作： <基本操作的定义>
}
（其中数据对象和数据关系就是逻辑结构，基本操作就是抽象运算）抽象数据类型中对数据对象和数据运算的声明，将对数据对象的表示和数据运算的实现分离。

在具体存储结构上实现某个抽象运算。或者可以定义为，对特定问题求解方法的一种描述，是指令的优先序列，其中每一条指令表示一个或多个操作

（1）算法的重要特性

（2）算法与程序的区别

程序1：违反了算法的可行性

void exam1()
{
 int x,y:
 y=0:
 x=5/y:
 printf("%d,%d\n",x,y);
 }

程序2：违反了算法的有穷性

void exam2()
{
 int n=2;
 while(n%2==0)
   n=n+2;
 printf("%d\n",n);
}

（3）评价算法的指标

程序设计语言表示算法：读入两个整数x、y，要求交换它们的值（程序2、3可以将两变量的值成功交换）

程序1（传值）：这个交换的是形式参数，并不是变量本身

void swap1(int x,int y)
{
 int tmp;
 temp=x;
 x=y;
 y=temp;
}

程序2（传递指针）：x和y的指针分别指向不同变量的值

void swap2(int *x,int *y)
{
 int tmp;
 temp=*x;
 *x=*y;
 *y=temp;
}

程序3（传引用）：x和y的分别指向不同变量的引用

void swap3(int &x,int &y)
{
 int tmp;
 temp=x;
 x=y;
 y=temp;
}

注：用时短的算法不一定是好算法，因为程序执行的环境不同、实现语言等其他因素也有影响

（1）用基本运算的次数度量算法的时间复杂度

算法的构成：一个算法是由控制结构（顺序、分支和循环）和原操作（固有数据类型的操作，如比较、加减乘除等）构成；算法时间取决于二者的综合效果。

a.从算法中选取一种对于所研究的问题来说是基本运算的原操作（简称为基本运算）
b.算法执行时间大致为基本运算所需的时间与其运算次数的乘积
c.基本运算的一般是最深层循环内的语句

（2）算法的时间复杂度

（3）算法的时间复杂度的表示法

”O“：表示时间复杂度的”量级“；随问题规模n的增大，算法的执行时间增长率和f(n)的增长率相同
”O“的形式定义：若f(n)是正整数n的一个函数，存在一个正常数C和n_0，使得当n>=n_0时，有T(n)<=C*f(n)，则记T(n)=O(f(n))，实质是当n趋于无穷大时，T(n)/f(n)=C
例子：T(n)=3(n²)-5n+10000=O(n²)，指定正常数C=3，当n>2000时，有3(n²)-5n+10000<3(n²)，只求出T(n的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能客观的反映出当n增长到很大时算法的是时间性能；算法只关心n很大时的结果。

（4）复杂度的量级
O(1)<O(log2(n))<O(n)<O(nlog2(n))<O(n²)<O(n³)<O(2ⁿ)<O(n!)
在这里插入图片描述