文档介绍：算法概述
算法必须具备的四个性质:
输入: 有零个或多个由外部提供的量作为算法的输入
输出: 算法产生至少一个量作为输出.
确定性: 组成算法的每条指令是清晰的,无歧义的.
有限性: 在执行了有穷步骤后运算终止(程序则可以不满足此条性质,如操作系统,无限循环)
写出算法复杂性的渐近性态的数学表达式:
(能写出上阶函数即可)如:
算法的复杂性分为:时间复杂性需要时间资源的量;空间复杂性需要的空间资源的量
程序所需要的空间主要由指令空间,数据空间,环境栈空间构成:
会分析程序段的时间复杂度
一次冒泡
A、template<class T>
void Bubble(T a[ ], int n)
{// 计算a[0:n-1]中最大的元素通过冒泡移到右边
for( int i =1;i<n; i++)
if( a[i]>a[i+1]) swap(a[i], a[i+1]);
}
B、template<class T>
void BubbleSort(T a[ ], int n)
{// 计算a[0:n-1]中的n个元素通过冒泡排序
for( int i =n;i>1; i--)
Bubble(a,i);
}
第二章递归与分治策略
递归的概念(根据递归公式,能写出递归算法)
如:
递归函数如下:
A、int Factorial(int n)
{
if (n==0) return 1;
return n*Factorial(n-1);
}
B、
递归概念:一个直接或间接地调用自身的算法称为递归算法;一个使用函数自身给出定义的函数称为递归函数
递归缺点:消耗时间空间多优点:容易实现理解
递归小结
优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。
缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
2、分治法
分治法的基本思想是讲一个规模为N的问题分解成K个规模较小的子问题,这些子问题互相独立且与原问题相同。递归的解这些子问题,然后将子问题的解合并得到原问题的解。
二分搜索方法的基本算法描述和基本思想
基本思想:
二分搜搜索的基本思想是将N个元素分成个数大致相同的两半,去a【n/2】与x作比较,如果x=a【n/2】,则找到了x,算法中止。如果小于,则只要在数组的a的左半部继续搜索x;如果大于,则只要在数组a的右半部继续搜索x
二分搜索算法
template<class T>
int BinarySearch( T a[], const T& x, int n)
{//在a[0]<=a[1]<=···<=a[n-1]中搜索x
//如果找到,则返回所在位置,否则返回–1
int left= ; int right= ;
while( ){
int middle= ;
if(x==a[middle]) return middle;
if(x>a[middle]) left= ;
else right= ;
}
return –1; //未找到x
}
合并排序的具体算法和基本思想:
合并排序算法是用分治法的策略实现对N个