文章目录
一、算法的概念
二、插入排序
1.用玩扑克的方式解释插入排序
2.插入排序的算法如下:
(2)如何严格证明这个算法是正确的?
3.算法的时间复杂度分析
(1)比较评价算法的好坏,一个重要的标准就是算法的时间复杂度
(2)在分析算法的时间复杂度时,我们更关心最坏情况而不是最好情况
(3)如何证明是2n^2+3lgn和 n ^2是同一量级的?
(4)几种常见的时间复杂度函数按数量级从小到大的顺序
(5)Small-O notation和Big-O notation
四、归并排序:分而治之
1.插入排序与归并排序的区别
2.归并排序的步骤
五、快速排序:分而治之
1.快排的核心思想
2.时间复杂度
六、线性查找
1.任意输入字符串中找出某个字母的位置并返回这个位置
2.习题
七、折半查找
1.在有序的序列里查找,可用折半查找
2.如何保证程序的正确性?
3.习题
一、算法的概念
(1)算法(Algorithm) 是将一组输入转化成一组输出的一系列计算步骤,其中每个步骤必须能在有限时间内完成。
(2)
二、插入排序
1.用玩扑克的方式解释插入排序
要点在于:
(1)前提:每次插入新的值时,前面的序列都是有序的
(2)但和插入扑克牌有一点不同,不可能在两个相邻的存储单元之间再插入一个单元,因此要将插入点之后的数据依次往后移动一个单元。
2.插入排序的算法如下:
(1)运行结果如下:
(2)如何严格证明这个算法是正确的?
总结:
这里的第一条就相当于递归的Base Case
第二条就相当于递归的递推关系。这再次说明了递归和循环是等价的
3.算法的时间复杂度分析
(1)比较评价算法的好坏,一个重要的标准就是算法的时间复杂度
这里有一个问题,m不是个常数,也不取决于输入长度n,而是取决于具体的输入数据。
(a)在最好情况下
数组 a 的原始数据已经排好序了, while 循环一次也不执行,总的执行时间是(c1+c2+c5)*n-(c1+c2+c5),可以表示成an+b的形式,是n的线性函数(Linear Function)。
(b)在最坏情况(Worst Case) 下
所谓最坏情况是指数组 a 的原始数据正好是从大到小排好序的
(c)平均情况(Average Case)
(2)在分析算法的时间复杂度时,我们更关心最坏情况而不是最好情况
(3)如何证明是2n^2+3lgn和 n ^2是同一量级的?
(4)几种常见的时间复杂度函数按数量级从小到大的顺序
(5)Small-O notation和Big-O notation
四、归并排序:分而治之
1.插入排序与归并排序的区别
2.归并排序的步骤
(1)代码如下
(2)执行结果如下
(3)代码解释如下:
首先是sort函数:
sort 函数把a[start…end]平均分成两个子序列,分别是a[start…mid]和a[mid+1…end],对这两个子序列分别递归调用 sort 函数进行排序,然后调用 merge 函数将排好序的两个子序列合并起来。
接着是merge函数:
合并的过程很简单,每次循环取两个子序列中最小的元素进行比较,将较小的元素取出放到最终的排序序列中,如果其中一个子序列的元素已取完,就把另一个子序列剩下的元素都放到最终的排序序列中
(4)归并排序的调用过程如下:
(5)归并排序的复杂度
merge函数的时间复杂度为
sort函数的时间复杂度为
总的时间的复杂度为:
五、快速排序:分而治之
define N 某个数;
int a[N];
int partition(int start,int end)
{
int i=start;
int j=end;
int base=a[i];
while (i!=j){
while (a[j]>=base && istart){
mid=partition(start,end);
quicksort(start,mid-1);
quicksort(mid+1,end);
}
}
1.快排的核心思想
先找到一个基数(若是最左边的为基数,升序排列),从右边开始寻找小于基数的数字,然后从左边开始寻找大于基数的数,找到了就交换,直到这两端遍历的i和j碰头为止。
2.时间复杂度
N:需要排序的元素个数
最差时间复杂度O(N^2);
平均时间复杂度O(NlogN),这里的log是以2为底
六、线性查找
1.任意输入字符串中找出某个字母的位置并返回这个位置
(1)写一个 indexof 函数,从任意输入字符串中找出某个字母的位置并返回这个位置,如果找不到就返回-1:
代码如下:
(2)时间复杂度是:O(n)
2.习题
(1)
没有
(2)
int partition(int start, int end)
{
int i=start,j=end;
int base=a[start];
while (i!=j)
{
while (i=base)
j--;
while (istart)
mid=partition(start,end);
int i=mid;
if (k==i)
return i;
else if (k>i)
return partition(mid+1,end,k)
else
return partition(start,mid-1,k)
}
七、折半查找
1.在有序的序列里查找,可用折半查找
(1)代码如下:
(2)折半查找Binary Search的含义
2.如何保证程序的正确性?
(1)接着上面的二分查找的eg去讲,在这个a[start…end]范围之外的数组 a 的元素中一定不存在 number 这个元素。
以下为了书写方便,我们把这句话表示成 mustbe(start, end, number) 。
解释:
(a)注意这个算法有一个非常重要的前提: a 是排好序的
(b)从更普遍的意义上说,函数的调用者(Caller) 和函数的实现者(Callee,被调用者) 之间订立了一个契约(Contract) ,在调用函数之前,Caller要为Callee提供某些条件,比如确保 a 是排好序的,确保a[start…end]都是有效的数组元素而没有
访问越界,这称为Precondition。然后Callee对一些Invariant进行维护(Maintenance) ,这些Invariant保证了Callee在函数返回时能够对Caller尽到某些义务,比如确保“如果 number 在数组 a 中存在,一定能找出来并返回它的位置,如果 number 在数组 a 中不存在,一定能返回-1”,这称为Postcondition。
(c)测试一个函数是否正确需要把Precondition、Maintenance和Postcondition这三方面都测试到,比如 binarysearch 这个函数,即使它写得非常正确,既维护了Invariant也保证了
Postcondition,如果调用它的Caller没有保证Precondition,最后的结果也还是错的。
(2)我们编写几个测试用的Predicate函数,然后把相关的测试插入到 binarysearch 函数中
下面的是带有测试代码的折半查找:
说明:
(a)断言Assertion的作用如下:
(b)测试代码只在开发和调试时有用。
如果正式发布(Release) 的软件也要运行这些测试代码就会严重影响性能了,如果在包含 assert.h 之前定义一个 NDEBUG 宏(表示No Debug) ,就可以禁用 assert.h 中的 assert 宏定义,这样代码中的所有 assert 测试都不起作用了:
(c)总结下
在实际工作中我们要测试的代码绝不会像 binarysearch 这么简单,而我们编写的测试函数往往都很简单,比较容易保证正确性,也就是用简单的、不容易出错的代码去测试复杂的、容易出错的代码。
3.习题
int binarysearch(int number)
{
int mid, start=0,end=N-1;
while (start<=end)
{
mid=(start+end)/2;
if(numbera[mid])
start=mid+1;
else
{
while (a[mid--]==number);
return mid;
}
}
}
double mysqrt(double y)
{
double mid,start=0,end=y;
while (start<=end)
{
mid=(start+end)/2;
if ((abs(pow(mid,,2)-y)<0.001)
return mid;
else if ((pow(mid,,2)