一.递归 汉诺塔算法:把A柱的盘子,移动到C柱上,最少需要移动几次,大盘子只能在小盘子下面 1.当盘子的个数为n时,移动的次数应等于2^n – 1 2.描述盘子从A到C: (1)如果A只有一个圆盘,可以直接移动到C: (2)如果A有N个圆盘,可以看成A有1个圆盘(底盘) + (N-1)个圆盘,首先需要把 (N-1) 个圆盘移动到 B,然后,将 A的最后一个圆盘移动到C,再将B的(N-1)个圆盘移动到C. 3.代码 i = 0 def move(n, a, b, c): global i if n
排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升. 1.插入排序 插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序. def insertion_sort(old_list): n=len(old_list) k=0 for i in range(1,n): temp=old_list[i] j=i while j>0 and temp<old_list[j-1]: old_list[j]=old_list[j-1] j=j-1
1.快速排序 过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小 一般选取第一个数作为关键数据k,我们要把比k小的所有数据移到它的左面,从后往前找第一个比它小的数据,交换位置 比k大的数据移到它的右面,从前往后找第一个比它大的数据,交换位置,完成一个循环. def quick1_sort(list): if len(list) < 2: return list else: key = list[0] small = [i for i in list[1
1.选择排序 不断找到最小的(找最大的也是可以的) 首先拿到第一个,然后发现比它小的,记住下标.循环一轮,找到最小的数的位置 和 最左边的数交换位置 然后从第二个开始....和第二个交换位置,循环最后变得有序 #coding=utf-8 def select_sort(list): for i in range(len(list)): min = i for j in range(i+1,len(list)): if list[min]>list[j]: min = j list[min], l
一: #计算平均数,中位数和众数 #coding:utf-8 #计算平均数,中位数和众数 import random lst = [random.randint(0,10) for i in range(11)] s = sum(lst) length = len(lst) average = s*1.0 / length print "The average is:",average lst.sort()print "From small to bigger,",
目录: 一:大O记法 二:各函数高阶比较 三:常用算法和数据结构的复杂度速查表 四:常见的logn是怎么来的 一:大O记法 算法复杂度记法有很多种,其中最常用的就是Big O notation(大O记法): 对于其中的g(x)是关于操作元素数x为自变量的计算次数函数,而x趋近无穷大从而只留下最高项且忽略其常数项是为了集中看函数随着元素个数的大量增加后运行时间的增加速度从而用来衡量时间复杂度. e.g: for i in range(x): print(‘aha’) print(i) print(