江苏水利厅建设网站,河长制网站建设,广州网站优化步骤,wordpress 百度翻译插件1. 算法概念
1.1 什么是数据结构
存储#xff0c;组织数据的方式
1.2 什么是算法
实现业务目的的各种方法和思路算法是独立的存在#xff0c;只是思想#xff0c;不依附于代码和程序#xff0c;可以使用不同语言实现#xff08;java#xff0c;python#xff0c;c组织数据的方式
1.2 什么是算法
实现业务目的的各种方法和思路算法是独立的存在只是思想不依附于代码和程序可以使用不同语言实现javapythonc
1.2.1 算法的五大特性
输入 算法具有0个或多个输入输出 算法至少有1个或多个输出有穷性 算法在有限的步骤之后会自动结束循环而不会无限循环并且每一个步骤可以在可接受的时间内完成确定性 算法中每一个步骤都有确定的含义不会出现二义性可行性 算法的每一步都是可行的也就是说每一步都能够执行有限的次数完成
穷举法 将问题的答案一一列举根据判断条件判断答案是否合适
# 如果abc1000且a^2b^2c^2(abc为自然数)求出a, b, c所有可能的组合
import timestart_time time.time()
for a in range(0, 1001):for b in range(0, 1001):for c in range(0, 1001):if a**2 b**2 c**2 and abc 1000:print(a{0}, b{1}, c{2}.format(a, b, c))end_time time.time()
all_time end_time-start_time
print(all_time)执行结果 穷举法计算完成需要261秒
方法二
# 如果abc1000且a^2b^2c^2(abc为自然数)求出a, b, c所有可能的组合
# 列举abc所有可能的数值
import timestart_time time.time()
for a in range(0, 1001):for b in range(0, 1001):c 1000-a-bif a**2 b**2 c**2:print(a{0}, b{1}, c{2}.format(a, b, c))end_time time.time()
all_time end_time-start_time
print(all_time)执行结果 方法二计算完成仅需要0.3秒
1.3 时间复杂度
1.3.1 穷举法
循环次数 三次循环分别为1001次 1001次 1001次每次循环的步骤 1000 abc 3次 a**2 b**2 c**2 5次 print打印 2次 代码总执行次数 T 1001 * 1001 * 1001 * (532) 次 总结成时间复杂度表达式 当问题规模为n时 T(n) 10 * n³时间复杂度表示算法随着问题规模不断变化的最主要趋势, 衡量算法的量级大O计法将次要关系全部省略掉由最高次项表示最终生成一个表达式T(n) O(n³)
1.3.2 方法二
T(n) O(n2)
1.3.3 时间复杂度计算规则
基本操作 时间复杂度为O(1)顺序结构 时间复杂度按加法计算循环结构 时间复杂度按乘法计算分支结构 时间复杂度取最大值判断算法效率 只需要关注操作数量的最高次项其他次要项和常数项可忽略在没有特殊说明时我们所分析的算法时间复杂度都是指最坏时间复杂度
1.3.4 常见时间复杂度
举例时间复杂度非正式术语 12 O(1) 常数阶 2n3 O(n) 线性阶 3n 22n1 O(n 2) 平方阶 5log 2n20 O(logn) 对数阶 6n 32n 23n4 O(n 3) 立方阶
消耗时间从小到大 O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(n!)
1.4 空间复杂度
空间复杂度(S(n))定义该算法所消耗的存储空间临时占用存储空间大小的度量
2. 数据结构
概念 存储、组织数据的方式相互之间存在一种或多种特定关系的数据元素的集合往往同高效的算法有关作用 相同的数据用不同的方式也就是不同的数据结构存储那么带来的运行或存储效率也是不同的
示例 存储方式一列表
people1 [{name:aaa, age:18}, {name:bbb,age:19}]
# 查找bbb
for peo in people1:if peo[name] bbb:print(over)时间复杂度为O(n)
存储方式二字典
people1 {{name:aaa, age:18}, {name:bbb,age:19}}
# 查找bbb
if bbb in people1:print(over)时间复杂度为O(1)
算法和数据结构的区别 数据结构只是静态描述了数据元素的关系高效的程序需要再在数据结构的基础上设计和选择算法算法是为了解决实际问题而设计的数据结构是算法需处理问题的载体
2.1 数据结构的分类
线性结构表中各个节点具有线性关系(栈队列)非线性结构 表中各个节点具有多个对应关系(树图)
3. 顺序表
顺序表 将元素顺序的放在一块连续的存储区里元素间的关系由他们的存储顺序自然表示链表 将元素存放在通过链接构造起起来的一系列存储块中存储区是非连续的
3.1 顺序表分类
一体式结构分离式结构无论是一体式结构还是分离式结构在获取数据的时候直接通过下标偏移就可以找到数据所在空间的地址而无需遍历后才可以获取地址所以顺序表在获取地址操作的时间复杂度为O(1)顺序表完整信息 数据区信息区即元素存储容量和当前表中已有元素的个数 顺序表的扩充 每次扩充增加固定数目和存储位置如每次扩充10个位置可称为线性增长 特点节省空间但扩充操作频繁操作次数多每次扩充容量加倍如每次扩充增加一倍的存储空间 特点减少了扩充的次数但可能会浪费空间资源以空间换取时间推荐的方式 元素存储区替换顺序表存储连续空间如果下方扩充空间被占用只能整体搬迁
3.2 顺序表增加删除元素
3.2.1 增加元素
尾端加入元素时间复杂度为O(1)非保序的加入元素不常见时间复杂度为O(1)保序的元素加入时间复杂度为O(n)
3.2.2 删除元素
尾端删除元素时间复杂度为O(1)非保序的删除元素不常见时间复杂度为O(1)保序的元素删除时间复杂度为O(n)
4. 链表
4.1 链表结构
单链表 链表的一种形式每个节点包含两个域一个元素域和一个链接域这个链接指向链表中下一个节点而最后一个节点的链接域指向一个空值表元素域elem用来存放具体的数据链接域next用来存放下一个节点位置变量head指向链表的头结点的位置从head出发能找到表中任意节点
# item 存放元素
# next 标识下一个节点
class SingleNode:def __init__(self, item):self.item item# 标识下一个节点self.next None# 单链表实现
# head 首结点
class SingleLink:def __init__(self, nodeNone):# 首结点self.head node
# 结点
node1 SingleNode(10)
print(node1.item)
print(node1.next)
# 链表
link1 SingleLink()
print(link1.head)
link2 SingleLink(node1)
print(link2.head)
print(link2.head.item)4.2 链表的代码实现
---- 判空长度遍历增加删除
# 链表节点实现
# item 存放元素
# next 标识下一个节点
class SingleNode:def __init__(self, item):self.item item# 标识下一个节点self.next None# 单链表实现
# head 首结点
class SingleLink:def __init__(self, nodeNone):# 首结点self.head node# 判断链表是否为空def is_empty(self):if self.head is None:return Trueelif self.head is not None:return False# 获取链表的长度def length(self):cur self.headcount 0while cur is not None:count 1cur cur.nextreturn count# 遍历链表def traverse(self):cur self.headwhile cur is not None:print(cur.item)cur cur.next# 头部增加结点def add(self, item):node SingleNode(item)node.next self.headself.head node# 尾部增加结点def append(self, item):node SingleNode(item)# 判断是否为空链表if self.is_empty():self.head nodeelse:cur self.head# 找到尾结点while cur.next is not None:cur cur.nextcur.next node# 指定位置增加结点def insert(self, pos, item):if pos 0:#头部增加新结点self.add(item)elif pos self.length():self.append(item)else:# 游标cur self.head# 计数count 0# 新结点node SingleNode(item)# 找到插入位置的前一个结点while count pos -1:cur cur.nextcount 1# 完成插入新结点node.next cur.nextcur.next node# 删除结点def remove(self, item):cur self.headpre Nonewhile cur is not None:# 找到了删除元素if cur.item item:# 要删除的元素在头部if cur self.head:self.head cur.nextelse:# 要删除元素不在头部pre.next cur.nextreturnelse:# 没有找到要删除元素pre curcur cur.nextdef search(self, item):# 游标cur self.headwhile cur is not None:if cur.item item:return Truecur cur.nextreturn Falseif __name__ __main__:# 结点node1 SingleNode(10)print(node1.item)print(node1.next)# 链表hylink1 SingleLink()print(link1.head)link2 SingleLink(node1)print(link2.head)print(link2.head.item)# 判空print(link1.is_empty())print(link2.is_empty())# 长度print(link1.length())print(link2.length())# 遍历print(link2.traverse())# 头部增加结点link2.add(9)link2.traverse()# 尾部增加结点link2.append(11)link2.traverse()# 指定位置增加结点link2.insert(2, 7)link2.traverse()link2.insert(-1, 7)link2.traverse()link2.insert(9, 7)link2.traverse()# 删除结点link2.remove(9)link2.traverse()# 查找结点是否存在print(link2.search(7))print(link2.search(9))5. 栈
运算受限的线性表只允许在表的一端进行插入和删除这一端被称为栈顶另一端被称为栈底 符合先进后出的特点
5.1 栈的作用
计算机系统里面CPU结构的一部分局部变量在函数使用完毕后销毁存放进栈即不浪费空间又能及时销毁
# 使用列表封装改造为栈尾部操作效率更高
class Stack:栈def __init__(self):self.__items []def push(self, item):进栈self.__items.append(item)def pop(self):出栈self.__items.pop()def travel(self):遍历a []for item in self.__items:a.append(item)return aif __name__ __main__:my_stack Stack()my_stack.push(10)my_stack.push(20)my_stack.push(30)print(-------进栈---------)a my_stack.travel()print(a)my_stack.pop()print(-------出栈后---------)a my_stack.travel()print(a)6. 队列
特殊的线性表只允许在头部进行删除操作在尾部进行添加操作插入操作端称为队尾删除操作称为队头 符合先进先出的特点
6.1 队列的作用
任务处理类系统先把用户发送过来的请求存储在队列中然后开启多个应用程序从队列中取任务进行处理起到缓冲压力的作用
6.2 队列代码实现
# 使用列表封装改造成队列
# 创建一个空队列
class Queue:def __init__(self):self.items []# 队列尾部添加元素def enqueue(self, item):self.items.append(item)# 队列头部删除数据def dequeue(self):self.items.pop(0)# 判断队列为空def is_empty(self):return self.items []# 返回队列大小def size(self):return len(self.items)def traverse(self):item_list []for i in self.items:item_list.append(i)return item_listif __name__ __main__:print(--------进队列--------)q Queue()q.enqueue(a)q.enqueue(b)q.enqueue(c)item_list q.traverse()print(item_list)print(--------出队列--------)q.dequeue()item_list q.traverse()print(item_list)is_empty q.is_empty()print(--------判断队列为空--------)print(is_empty)print(--------返回队列大小--------)print(q.size())6.3 双端队列
具有队列和栈的数据结构元素可以从两端任意插入弹出其限定插入弹出操作必须在两端进行 可以在队列任意一端入队和出队
6.4 双端队列代码实现
class Dequeue:双端队列def __init__(self):self.items []def is_empty(self):是否为空判断return self.items []def size(self):返回队列大小return len(self.items)def add(self, item):头部增加数据self.items.insert(0, item)def add_last(self, item):尾部添加数据self.items.append(item)def remove(self):头部删除数据self.items.pop(0)def remove_last(self):尾部删除数据self.items.pop()def traverse(self):item_list []for item in self.items:item_list.append(item)return item_listif __name__ __main__:dequeue Dequeue()print(dequeue.is_empty())print(dequeue.size())print(--------头部添加数据--------)dequeue.add(1)dequeue.add(2)item_list dequeue.traverse()print(item_list)print(--------尾部添加数据--------)dequeue.add_last(3)dequeue.add_last(4)dequeue.add_last(5)item_list dequeue.traverse()print(item_list)print(--------头部删除数据--------)dequeue.remove()item_list dequeue.traverse()print(item_list)print(--------尾部删除数据--------)dequeue.remove_last()item_list dequeue.traverse()print(item_list) 7. 算法
排序算法稳定性在待排序的序列中存在多个关键字记录若经过排序这些记录的相对次序保持不变则称这种排序算法是稳定的否则是不稳定的
不稳定的排序算法选择排序快速排序希尔排序堆排序稳定的排序算法冒泡排序插入排序归并排序基数排序
7.1 冒泡排序
时间复杂度最差O(n2)最优O(n)算法稳定性稳定
def bubble_sort(alist):冒泡排序# 控制比较轮数for j in range(0, len(alist)-1):# 计数count 0# 控制每一轮的比较次数for i in range(0, len(alist)-j-1):# 比较相邻的两个数字不符合要求交换位置if alist[i] alist[i1]:alist[i], alist[i1] alist[i1], alist[i]count 1# 如果遍历一遍发现没有数字交换退出循环证明数列是有序的if count 0:breakif __name__ __main__:alist [5, 4, 3, 2, 1]bubble_sort(alist)print(alist)7.2 选择排序
工作原理第一次从待排序的数据中选出最小或最大的元素存放在序列的起始位置然后再从剩余的未排序的元素中找出最小或最大的元素然后放到已排序的序列的末尾以此类推直到全部待排序的数据元素个数为0 时间复杂度最差O(n2)最优O(n2)算法稳定性不稳定
def select_sort(alist):选择排序# 列表的长度n len(alist)# 控制比较轮数for j in range(0, n-1):# 假定最小值下标min_index j# 控制比较次数for i in range(j1, n):# 进行比较最小值if alist[i] alist[min_index]:min_index i# 如果假定的最小值发生了变化那么我们就进行交换if min_index ! j:alist[min_index], alist[j] alist[j], alist[min_index]if __name__ __main__:alist [5, 4, 3, 2, 1]select_sort(alist)print(alist)7.3 快速排序
基本思路通过一趟排序将要排序的数据独立分割成两个部分其中一部分的所有数据都比另一部分所有数据都要小然后以此方法对这两部分的数据分别进行快速排序整个排序过程可以递归执行以此达到整个数据变成有序序列 排序流程如下
首先设定一个分界值通过分界值将数组分为左右两个部分将大于或等于分界值的数据集中分布在右边小于分界值的数据集中分布在左边此时左边部分中各元素都小于分界值右边部分各元素都大于等于分界值左边和右边的数据可以独立排序对于左侧数据又可以取一个分界值将该部分分为左右两部分同样在左边放置最小值右边放置最大值右侧数据也做类似处理重复上述步骤可以看出这是一个递归定义通过递归将左侧排好序后再递归排好右侧部分顺序当左右两个部分各数据排序完成后整个数组排序也就完成了
时间复杂度最差O(n2)最优O(nlogn)算法稳定性不稳定
def quick_sort(alist, start, end):快速排序# 递归结束条件if start end:return# 界限值mid alist[start]# 左右游标left startright endwhile left right:while alist[right] mid and left right:right right - 1# 从右边开始找寻小于mid的值归类到左边alist[left] alist[right]# 从左边开始找寻小于mid的值归类到右边while alist[left] mid and left right:left left 1alist[right] alist[left]# 循环一旦结束 证明找到了mid的值alist[left] mid# 递归操作quick_sort(alist, start, left - 1)quick_sort(alist, right 1, end)if __name__ __main__:alist [10, 9, 8, 7, 7, 6, 5, 9, 3, 2, 1]quick_sort(alist, 0, len(alist) - 1)print(alist) 7.4 插入排序
直接将一个数据插入到已经排好序的有序的数据中从而得到一个新的个数加一的有序数据算法适用于少量数据排序 组成
有序的数字默认数组的第一个数字为有序的第一部分部分无序的数字除了第一个数字之外的数字可以认为是无序的第二部分
时间复杂度最差O(n2)最优O(n)算法稳定性稳定
def insert_sort(alist):插入排序n len(alist)# 控制轮数for j in range(1, n):# 找到合适的位置存放无序数据for i in range(j, 0, -1):if alist[i - 1] alist[i]:alist[i], alist[i - 1] alist[i - 1], alist[i]else:breakif __name__ __main__:alist [10, 8, 9, 7, 5, 4, 2, 3, 1]insert_sort(alist)print(alist)7.5 二分查找
折半查找效率较高的查找方法 原理
将数值分为三部分中值前中值和中值后将要查找的值依次与中值进行比较若小于中值则在中值前面找若大于中值则在中值后面找等于中值则返回必须采用顺序表存储结构必须按关键字大小有序排列
时间复杂度最差O(logn)最优O(1)算法稳定性稳定
7.5.1 递归版本
def binary_search(alist, item):二分查找# 数列长度n len(alist)# 递归结束条件if n 0:return False# 中间值mid n // 2if alist[mid] item:return Trueelif alist[mid] item:return binary_search(alist[:mid], item)elif alist[mid] item:return binary_search(alist[mid 1:], item)if __name__ __main__:my_list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]print(binary_search(my_list, 10))print(binary_search(my_list, 11))7.5.2 非递归版本
def binary_search(alist, item):二分查找# 数列长度n len(alist)# 设置起始位置获取中间值start 0end n - 1while start end:# 中间值mid start end // 2if alist[mid] item:return Trueelif alist[mid] item:start mid 1elif alist[mid] item:end mid - 1# 没有找到想要找的数字return Falseif __name__ __main__:alist [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]print(binary_search(alist, 10))print(binary_search(alist, 11))8. 树
具有模拟树状结构性质的集合它是由n(n1)个有限结点组成一个具有层次关系的集合把他叫做树
每个节点有零个或多个子节点没有父节点的节点叫做根节点每一个非根节点只有一个父节点除了根节点以外每个子节点可以分为多个不相交的树
8.1 树的相关术语
节点的度 一个节点含有子节点的个数树的度 一棵树中最大节点的度称为树的度叶节点或终端节点 度为0的节点父节点 若一个节点含有子节点则这个节点称为其子节点的父节点子节点 一个节点含有的子树的根节点称为该节点的子节点兄弟节点 具有相同父节点的节点互称兄弟节点节点层次 从根开始定义根为第一层根的子节点为第二层以此类推树的高度和深度 树种节点的最大层次堂兄弟节点 父节点的同一层节点互称为堂兄弟节点节点祖先 从根到该节点所经历分支上的所有节点子孙 以某节点为根的子树中任意节点森林 由m(m0)棵互不相交的树的集合
8.2 树的种类和存储
无序树 树中任意节点的子节点之间没有顺序关系也称为自由树有序树 树中任意节点的子节点之间有顺序关系 霍夫曼树用于信息编码 带权路径最短的二叉树称为霍夫曼树或最优二叉树B树 一种对读写操作进行优化的自平衡的二叉查找树能够保持数据有序拥有多于两个的子树 二叉树 每个节点最多含有两个子树 完全二叉树 对于一颗二叉树假设其深度为d(d1)除了第d层之外其他各层的节点数目均已达到最大值且d层所有节点从左到右连续的紧密排列这样的二叉树被称为完全二叉树其中满二叉树的定义是所有叶节点都在最底层的二叉树平衡二叉树AVL树 当且仅当任何节点的两颗子树的高度差不大于1的二叉树排序二叉树(二叉搜索树、有序二叉树) 要求①若左子树不空则左子树上所有节点的值均小于它的根节点的值②若右子树不空则右子树上所有节点的值均大于根节点的值③左右子树分别也为排序二叉树④排序二叉树包含空树
8.3 二叉树的存储
顺序存储 将数据结构存储在固定的数组中虽然遍历上有优势但是所占空间大是非主流的二叉树存储方式链式存储 由于对节点的个数无法掌握常见的树的存储表示都转换成二叉树进行处理子节点最多个数为2主流二叉树存储方式指针域个数不定
8.4 树的应用场景
xml、html等编写这些东西的解析器的时候不可避免的需要用到树路由协议就是使用了树的算法mysql数据索引文件系统的目录结构很多经典的AI算法都是树搜索机器学习中的decision tree也是树结构
8.5 二叉树的性质
在二叉树上的第i层上至多有2i-1个节点(i0)深度为k的二叉树至多有2k-1个节点(k0)对于任意一颗二叉树如果其子叶节点数为N0而度数为2的节点总数为N2则N0 N2 1最多有n个节点的完全二叉树的深度必为log2(n1)对于完全二叉树若从上到下从左到右编号则编号为i的节点其左孩子编号必定为2i右孩子编号必为2i1其父节点的编号必为i//2 (i1时为根除外)
8.6 二叉树的遍历
广度优先遍历 可以找到最短路径深度优先遍历
8.6.1 广度优先遍历
class Node(object):节点类def __init__(self, item):self.item itemself.lchild Noneself.rchild Noneclass BinaryTree(object):完全二叉树def __init__(self, nodeNone):self.root nodedef add(self, item):添加节点if self.root is None:self.root Node(item)# 队列queue []# 从尾部添加数据queue.append(self.root)while True:# 从头部取出数据node queue.pop(0)# 判断左右子树是否为空if node.lchild is None:node.lchild Node(item)returnelse:queue.append(node.lchild)if node.rchild is None:node.rchild Node(item)returnelse:queue.append(node.rchild)def breath_traversal(self):广度优先遍历if self.root is None:return# 队列queue []tree_list []# 添加数据queue.append(self.root)while len(queue)0:# 取出数据node queue.pop(0)print(node.item)tree_list.append(node.item)# 判断左右子节点是否为空if node.lchild is not None:queue.append(node.lchild)if node.rchild is not None:queue.append(node.rchild)return tree_listif __name__ __main__:tree BinaryTree()tree.add(a)tree.add(b)tree.add(c)tree.add(d)tree.add(e)tree.add(f)tree.add(g)tree.add(h)tree.add(i)tree.add(j)tree.add(k)tree_list tree.breath_traversal()print(tree_list)8.6.2 深度优先遍历
先序优先遍历 根 左 右中序优先遍历 左 根 右后序优先遍历 左 右 根
class Node(object):节点类def __init__(self, item):self.item itemself.lchild Noneself.rchild Noneclass BinaryTree(object):完全二叉树def __init__(self, nodeNone):self.root nodedef add(self, item):添加节点if self.root is None:self.root Node(item)# 队列queue []# 从尾部添加数据queue.append(self.root)while True:# 从头部取出数据node queue.pop(0)# 判断左右子树是否为空if node.lchild is None:node.lchild Node(item)returnelse:queue.append(node.lchild)if node.rchild is None:node.rchild Node(item)returnelse:queue.append(node.rchild)def breath_traversal(self):广度优先遍历if self.root is None:return# 队列queue []tree_list []# 添加数据queue.append(self.root)while len(queue)0:# 取出数据node queue.pop(0)print(node.item)tree_list.append(node.item)# 判断左右子节点是否为空if node.lchild is not None:queue.append(node.lchild)if node.rchild is not None:queue.append(node.rchild)return tree_listdef preorder_traversal(self, rootNone):先序遍历if root is not None:print(root.item, end)self.preorder_traversal(root.lchild)self.preorder_traversal(root.rchild)def inorder_traversal(self, rootNone):中序遍历if root is not None:self.inorder_traversal(root.lchild)print(root.item, end)self.inorder_traversal(root.rchild)def postorder_traversal(self, rootNone):后序遍历if root is not None:self.postorder_traversal(root.lchild)self.postorder_traversal(root.rchild)print(root.item, end)if __name__ __main__:tree BinaryTree()tree.add(a)tree.add(b)tree.add(c)tree.add(d)tree.add(e)tree.add(f)tree.add(g)tree.add(h)tree.add(i)tree.add(j)tree.add(k)tree.preorder_traversal(tree.root)tree.inorder_traversal(tree.root)tree.postorder_traversal(tree.root)
