我微软的忠实粉丝,从进入码农这个行业一直都在C#语言,.net平台,asp.net这个框架。过年回家家里有弟妹已经升初中了,学习相当紧张,但是我还是想要跟他们说要他们学习一门编程语言,不为什么可能想把他们也带入坑里面。他俩一直要我做他们的老师,教他们学习,哎看来是把我自己带入坑里面了,不过为了他们的学习之路我同意了。 对于最近流行的编程语言和一些政策信息我最终决定要教他们学习Python,正好我也换换思维,学习一下这个被码农们一直推崇的语言。

通过python学习算法,python学习算法

   
我微软的忠实粉丝,从进入码农这个行业一直都在C#语言,.net平台,asp.net这个框架。过年回家家里有弟妹已经升初中了,学习相当紧张,但是我还是想要跟他们说要他们学习一门编程语言,不为什么可能想把他们也带入坑里面。他俩一直要我做他们的老师,教他们学习,哎看来是把我自己带入坑里面了,不过为了他们的学习之路我同意了。 对于最近流行的编程语言和一些政策信息我最终决定要教他们学习Python,正好我也换换思维,学习一下这个被码农们一直推崇的语言。

   
其实学习也是需要有一定的目的性,带着目的性对于一个码农来说也会在自己的编程技术上有进一步的提高(我的个人想法)。正好最近我在研究算法,给自己的目标每日一类算法。于是我就用python来实现各种算法,这样既能学习这门语言也能达到我的目的。

     归并排序这是我今天的第一道算法题,原理:

归并算法基本思想是依据分治法来解决问题,1.分解:把长度为n的序列分解为n/2个序列。2.治理:对每个子序列分别调用归并排序,进行递归操作。当子序列长度为1时,序列本身有序,停止递归。3.合并:合并每个排序好的子序列。

  码农最主要还是代码

 1 class MergeAlgorithm:
 2     #将两个有序序列合并。
 3     def mergearray(self,first,last):
 4         temp=[]
 5         i=0
 6         j=0
 7 
 8         while j<len(first) and i<len(last):
 9             if first[j]<last[i]:
10                 temp.append(first[j])
11                 j+=1
12             else:
13                 temp.append(last[i])
14                 i+=1
15                 
16         if j==len(first):
17             for h in last[i:]:
18                 temp.append(h)
19         else:
20             for h in first[j:]:
21                 temp.append(h)
22 
23         return temp
24 
25     def mergesort(self, lists):
26         if len(lists) <= 1:
27             return lists
28         mid =int(len(lists) / 2)
29         left = mergesort(lists[0:mid])
30         right = mergesort(lists[mid:len(lists)])
31         return mergearray(left, right)

   这种写法就是按照C#的方式定义的类,然后调用,但是出现问题了

 yzc579亚洲城官网 1

什么鬼连自己的方法都不能用,哎看来我真的是在一种思维里面陷入的太深了。看看上面定义函数的时候发现参数里面多了一个self,在使用pycharm这个IDE自动显示出来,让我很郁闷最后查了一下关于这个关键字的用意”self
代表的是类的实例,代表当前对象的地址,而 self.class
则指向类”,参考)

如果又再次找度娘查原因,还是没有解决。最后还是回归到那句话”self
代表的是类的实例,代表当前对象的地址,而 self.class
则指向类”,于是把类改成”self.”,再次运行,oh,我的天了居然成功了。而且输出正确的结果yzc579亚洲城官网 2

就这么一点玩意折腾我半天了,看来我这个码农还真的是个码农啊。后面的路很长还在进一步研究,而且教小孩是一个很庞大的工程,一不小心就会误人子弟啊,所以是一定要小心加认真加尽责,就像我们对待每一份工作一样。

 

 

    

我微软的忠实粉丝,从进入码农这个行业一直都在C#语言,.net平台,asp.net这个框架。过年回家家里有弟…

《算法导论》的确是本了不起的书,以我现在的水平即使是开头的几章也难以理解透彻,于是就有了”与其问题越堆积越多,不如停下来整理一下所学“这样的念头。

   
其实学习也是需要有一定的目的性,带着目的性对于一个码农来说也会在自己的编程技术上有进一步的提高(我的个人想法)。正好最近我在研究算法,给自己的目标每日一类算法。于是我就用python来实现各种算法,这样既能学习这门语言也能达到我的目的。

1. 分治

维基百科——
在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

维基百科给出了分治法的定义,我相信这比我自己总结的要精确的多,因此直接引用。
分治策略是一种常用的算法策略,它是许多高效算法的基础,其中最耳熟能详的莫过于快速傅里叶变换与归并算法。
在分治策略中,我们递归的求解一个问题,在每层递归中应用下面三个步骤:

  1. 分解:将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小;
  2. 解决:递归的求解出子问题,如果子问题的规模够小,停止递归,直接求解。
  3. 合并:将子问题的解组合成原问题的解。

求解子问题时可能存在两种情况:

  1. 递归情况:子问题足够大,需要继续递归求解;
  2. 基本情况:子问题已经足够小,不再需要递归求解,可以直接得出当前子问题的解。

除了这两种与原问题形式相同的子问题情况外,还可能要求求解原问题不一样的子问题,我们将这些子问题的求解看做合并步骤的一部分。

     归并排序这是我今天的第一道算法题,原理:

2. 归并算法的例子

我们首先来看看最常见的归并排序算法,关于归并排序的说明实在太多,我相信任何一篇说明该方面的文章都要比我讲述的好,因此在此不再赘述归并排序的详细内容。
简单了解归并排序后,即可发现,归并排序算法完全遵循分治模式,直观上归并排序可以理解为——

  • 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列;
  • 解决:判断问题规模,若是足够小则直接求出答案,若是较大则继续分解问题,递归的求解答案;
  • 合并:合并两个已经完成排序的子序列以产生排序的答案。

在归并排序问题中,序列的长度为1时,达到上述的基本情况的要求,不需要做任何工作。因为长度为1的序列必定是有序的。
算法导论中的伪代码如下:

yzc579亚洲城官网 3

合并过程代码片段1

yzc579亚洲城官网 4

合并过程代码片段2

归并排序算法的关键是“合并”步骤中两个已排序序列的合并,这个过程多次调用并且不需要递归,因此我们设计一个辅助过程来实现。应该注意到的是该伪代码设计中使用了“哨兵“,即在数组的最后一个元素后多设一个单元的空间,存放一个特殊值(这里是∞),每当处理到∞
时即说明该数组的非哨兵元素都已经处理完毕。而∞
大于任意常量,因此无元素数组不会再被提取元素,后续循环会将未处理完的数组元素一一提取插入新数组。

yzc579亚洲城官网 5

分解过程代码片段

现在我们将过程MERGE作为一个子程序来调用,若p>=r,则子数组最多有一个元素,所以已经排好序。为了排序整个序列A={
A[1],A[2],…..,A[n]
},我们执行初始调用MEAGE-SORT(A,1,A.length),这里A.length=n。

归并算法基本思想是依据分治法来解决问题,1.分解:把长度为n的序列分解为n/2个序列。2.治理:对每个子序列分别调用归并排序,进行递归操作。当子序列长度为1时,序列本身有序,停止递归。3.合并:合并每个排序好的子序列。

3. 分析归并排序算法

  码农最主要还是代码

3.1 MERGE

我们首先分析MERGE的时间复杂度,假设第1行到第17行运行一次的代价分别为常量c1,c2….c17,合并后的数组长度为n1+n2=r-p+1=n,可分析得出——

  • 第1-3行仅执行一次,代价和为C1+C2+C3;
  • 第4,5行执行n1次,第6,7行执行n2次,代价和为n1*(C4+C5)+n2*(C6+C7);
  • 第8-11行执行一次,代价和为C8+C9+C10+C11;
  • 第12,13行执行n次,14-15行目的为将分数组L的元素逐个插入合数组A中,而L中只有n1个有效元素,因此该部分执行n1次,同理,16-17行执行n2次,代价和为:
    n*(C12+C13)+n1*(C14+C15)+n2*(C16+C17)。

将以上分析结果累加,常数项合并为CK,得时间复杂度

f(n) = n*(C12+C13)+n1*(C14+C15+C4+C5)+n2*(C16+C17+C6+C7)+CK
=Θ(n)+Θ(n1)+Θ(n2)+Θ(1)
=Θ(n)

 1 class MergeAlgorithm:
 2     #将两个有序序列合并。
 3     def mergearray(self,first,last):
 4         temp=[]
 5         i=0
 6         j=0
 7 
 8         while j<len(first) and i<len(last):
 9             if first[j]<last[i]:
10                 temp.append(first[j])
11                 j+=1
12             else:
13                 temp.append(last[i])
14                 i+=1
15                 
16         if j==len(first):
17             for h in last[i:]:
18                 temp.append(h)
19         else:
20             for h in first[j:]:
21                 temp.append(h)
22 
23         return temp
24 
25     def mergesort(self, lists):
26         if len(lists) <= 1:
27             return lists
28         mid =int(len(lists) / 2)
29         left = mergesort(lists[0:mid])
30         right = mergesort(lists[mid:len(lists)])
31         return mergearray(left, right)

3.2 总体

虽然归并排序在元素数并非偶数时仍然能工作,但为了简化分析过程,我们假定问题的规模是2的幂,这时每个分解步骤将产生规模正好为n/2的两个子序列。这个假设将不会影响结果的增长量级。
当有n>1个元素时,设运行时间为T(n),我们分解运行时间为:

  • 分解:分解步骤仅仅计算数组的中间位置,需要常量时间,时间复杂度为Θ(1);
  • 解决:递归的求解两个规模均为n/2的子问题,将贡献2T(n/2)的运行时间;
  • 合并:之前的分析可知在一个具有n个元素的子数组过程上MERGE需要Θ(n)的时间。
    由此可得出归并排序最坏情况的运行时间为

当n=1时,T(n) = Θ(1);
当n>1时,T(n)=2T(n/2)+Θ(n)。

画出递归树

yzc579亚洲城官网 6

归并算法递归树

有关递归树的内容之后再详细说明。简而言之,递归树中的每个节点都表示了该节点的代价。T(n)分解之后本身剩余的是合并的代价——Θ(n)=cn,分解后的两个T(n/2)的和是T(n)代价的另一部分,作为cn的两个叶节点,由此可知整棵树中所有节点的代价和即算法的代价。
将T(n)不断分解,直到分解到问题规模为1时,由于n是2的幂,因此需要经过lg(n)层分解。无论如何分解,算法最终都会将各个分数组合并成长度为n的有序数组,每层分解都相当于将长度为n的有序数组不断划分为小数组,即每层操作的数组长度和是不变的,和为n。而合并操作的时间复杂度为Θ(n),因此每层的代价和都为cn。
或者换个严谨些的方式来说,一般来说,若顶层为0层,顶层下的第i层有2i个节点,每个节点分解解决后合并时需要的代价为其自身的长度,即cn/(2i)。故每层的代价和为cn,一共有lg(n)+1层,因此整棵树的代价为cn(lg(n)+1)=cn+cn*lg(n)。
忽略低阶项和常量c后就得到了期望的结果Θ(nlg(n))。

   这种写法就是按照C#的方式定义的类,然后调用,但是出现问题了

4. 递归式

现在我们将上面所说的最坏情况的运行时间写成数学表达式的形式:

yzc579亚洲城官网 7

递归式

这就是递归式了。递归式与分治法是紧密相关的,因为使用递归式可以很自然的刻画分治算法的运行时间。一个递归式就是一个等式或不等式,它通过更小的输入上的函数值来描述一个函数。递归式有很多种形式,例如,算法可能会将问题分解成规模不等的子问题,如2/3和1/3的划分。同时,子问题的规模不必是原问题规模的一个固定比例,例如线性查找的递归式T(n)=T(n-1)+Θ(1)。
《算法导论》介绍了三种求解递归式的方法,即得出算法的”Θ“或”O“渐近界的方法:

  • 代入法:我们猜测一个界,然后使用数学归纳法证明这个界的正确性;
  • 递归树法:将递归式转换为一棵树,其节点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式;
  • 主方法:主方法可用于求解形如 T(n)=aT(n/b)+f(n)
    的递归式的界,其中a>=1,b>1,f(n)是一个给定的函数。这种形式的递归式很常见,它描述了一种算法:生成a个子问题,每个子问题的规模是原问题规模的1/b,分解和合并步骤总共花费时间为f(n)。

关于这三种方法的具体情况,我会将它整理在下一篇文章中。

参考文献:Thomas H.Cormen《算法导论》,机械工业出版社, 2006-9-1

 yzc579亚洲城官网 1

什么鬼连自己的方法都不能用,哎看来我真的是在一种思维里面陷入的太深了。看看上面定义函数的时候发现参数里面多了一个self,在使用pycharm这个IDE自动显示出来,让我很郁闷最后查了一下关于这个关键字的用意”self 代表的是类的实例,代表当前对象的地址,而
self.class
则指向类”,参考)

如果又再次找度娘查原因,还是没有解决。最后还是回归到那句话”self 代表的是类的实例,代表当前对象的地址,而
self.class
则指向类”,于是把类改成”self.”,再次运行,oh,我的天了居然成功了。而且输出正确的结果yzc579亚洲城官网 2

就这么一点玩意折腾我半天了,看来我这个码农还真的是个码农啊。后面的路很长还在进一步研究,而且教小孩是一个很庞大的工程,一不小心就会误人子弟啊,所以是一定要小心加认真加尽责,就像我们对待每一份工作一样。

 

 

    

Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注