网站的运营费用吗,php源码建站 一品资源,建筑设计说明,wordpress判断页面类型文章目录精通一个领域切题四件套算法算法的五个条件流程图数据结构数据与信息数据信息数据结构和算法数据结构算法时间复杂度空间复杂度数组 Array优点缺点数组和链表的区别时间复杂度链表 Linked List优点缺点时间复杂度单向链表双向链表循环链表双向循环链表堆栈 Stack队列 Q…
文章目录精通一个领域切题四件套算法算法的五个条件流程图数据结构数据与信息数据信息数据结构和算法数据结构算法时间复杂度空间复杂度数组 Array优点缺点数组和链表的区别时间复杂度链表 Linked List优点缺点时间复杂度单向链表双向链表循环链表双向循环链表堆栈 Stack队列 Queue优先队列 Priority Queue哈希表 Hash Table哈希函数设计原则树、⼆叉树⼆叉搜索树二叉树遍历常见算法递归 Recursion [rɪˈkɜːrʒn]分治 Divde Conquer [ˈkɑːŋkər]迭代法枚举法回溯法贪⼼算法Greedy Algorithms)广度优先搜索(Breadth-First-Search)深度优先搜索(Depth-First-Search)剪枝⼆分查找Binary Search)字典树Trie)位运算的运⽤Bitwise operations)动态规划Dynamic Programming)图无向图有向图加权图精通一个领域 Chunk it up切碎知识点 庖丁解⽜脉络连接 Deliberate practicing刻意练习 刻意练习练习缺陷、不舒服、弱点地⽅不爽、枯燥 Feedback获得反馈 即时反馈主动型反馈⾃己去找 ⾼手代码 (GitHub, LeetCode, etc.)第一视角直播 被动式反馈高手给你指点 code review教练看你打给你反馈
切题四件套
Clarification [ˌklærəfɪˈkeɪʃn] 阐明Possible solutions compare(time/space)optimal(加强 Coding多写Test cases
算法 为了解决某项工作或某个问题所需要有限数量的机械性或重复性指令与计算步骤。 算法的五个条件
输入0个或多个输入数据这些输入必须有清楚的描述或定义。输出至少有一个输出结果不可以没有输出结果。明确性每一个指令或步骤必须是简洁明确的。有限性在有限步骤后一定会结束不会产生无限循环。有效性步骤清楚且可行能让用户用纸笔计算而求出答案。
流程图 是一种通用的以图形符号来表示程序执行流程的工具也是常用描述算法的工具。 数据结构 主要是表示数据在计算机内存中所存储的位置及其模式 基本数据类型 不能以其他类型来定义的数据类型或称为标量数据类型 整数、浮点、布尔数据类型和字符类型等 结构化数据类型 也称为虚拟数据类型字符串、数组、指针、列表、文件等。 抽象数据类型 我们可以将一种数据类型看成是一种值的集合以及在这些值上所进行的运算及其所代表的属性所成的集合。是指一个数学模型以及定义在此数学模型上的一组数学运算或操作。 表示的是一种“信息隐藏”的程序设计思想以及信息之间某一种特定的关系模式。 数据结构可通过程序设计语言所提供的数据类型、引用及其他操作加以实现。 程序能否快速而高效地完成预定的任务取决于是否选对了数据结构 程序是否能清楚而正确地把问题解决取决于算法 数据结构 算法 高效的可执行程序 数据与信息
数据 指的是一种未经处理的原始文字、数字、符号或图形等 数值数据字符数据 信息 利用大量的数据经过有系统的整理、分析、筛选处理而提炼出来的而且具有参考价格以及提供决策依据的文字、数字、符号或图表。 数据结构和算法 学习它的“来历”自身的特点适合解决的问题实际的应用场景 要多辩证地思考多问为什么主动 内功、性能方面的问题时间复杂度、空间复杂度 学习数据结构最难的不是理解和掌握原理而是能灵活地将各种场景和问题抽象成对应的数据结构和算法。 数据结构 10个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、tire树 线性表 数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。 数组 链表 栈 队列 散列表 哈希表 树 二叉树二叉搜索树堆平衡二叉树 - 红黑树tire 树 图
算法 10个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法 六种基本算法思想 递归/回溯算法分治算法贪心算法动态规划枚举算法迭代算法 八种排序算法 冒泡排序 O(n^2)选择排序希尔排序基数排序计数排序插入排序 O(n^2)归并排序 O(nlogn)快速排序 O(nlogn) 搜索算法 广度优先深度优先 查找算法 线性表查找散列表查找树结构查找 字符串匹配 tire 其他 数论计算几何线性规划矩阵运算概率分析并查集拓扑网络
Data StructureAlgorithmArray 数组General CodingStack / Queue 栈/队列In-order/Pre-order/Post-order traversalPriorityQueue (heap) 优先队列Greedy 贪心算法LinkedList (single / double) 链表Recursion/Backtrace 递归/回溯Tree / Binary Tree 树/二叉树Breadth-first search 广度优先Binary Search Tree 二叉搜索树Depth-first search 深度优先HashTable 哈希表Divide and Conquer 分治Disjoint Set 并查集Dynamic Programming 动态规划TrieBinary Search 二分查找BloomFilterGraph 图LRU Cache
时间复杂度 大O时间复杂度表示法 大O时间复杂度实际上并不具体表示代码真正的执行时间而是表示代码执行时间随数据规模增长的变化趋势所以也叫做渐进时间复杂度简称时间复杂度。 时间复杂度表示的是一个算法执行效率与数据规模增长的变化趋势。 时间复杂度分析 只关注循环执行次数最多的一段代码 大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数只需要记录一个最大阶的量级就可以了。所以我们在分析一个算法、一段代码的时间复杂度的时候也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级就是整段要分析代码的时间复杂度。 加法法则总复杂度等于量级最大的那段代码的复杂度 如果 T1(n)O(f(n))T2(n)O(g(n))那么 T(n)T1(n)T2(n)max(O(f(n)), O(g(n))) O(max(f(n), g(n))). 乘法法则嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 如果 T1(n)O(f(n))T2(n)O(g(n))那么 T(n)T1(n)*T2(n)O(f(n))*O(g(n))O(f(n)*g(n)). 最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度 复杂度量级分为多项式量级和非多项式量级O(2^n)和O(n!)NP非确定多项式 问题 O(1): Constant Complexity: Constant 常数复杂度 只要代码的执行时间不随 n 的增大而增长这样代码的时间复杂度我们都记作 O(1)。或者说一般情况下只要算法中不存在循环语句、递归语句即使有成千上万行的代码其时间复杂度也是Ο(1)。jj O(log n): Logarithmic Complexity: 对数复杂度 O(n): Linear Complexity: 线性时间复杂度 O(nlogn)线性对数阶 O(n^2): N square Complexity 平⽅ O(n^3): N square Complexity ⽴方 O(2^n): Exponential Growth 指数 O(n!): Factorial 阶乘 空间复杂度 空间复杂度全称是渐进空间复杂度asymptotic space complexity表示算法的存储空间与数据规模之间的增长关系。 常见的空间复杂度就是 O(1)、O(n)、O(n2 ) 数组 Array 特点数组是一种线性表数据结构。它用一组连续的内存空间在进行数组的删除、插入操作时为了保持内存数据的连续性需要大量的数据搬移来存储一组具有相同类型的数据 优点
支持随机访问根据下标随机访问的时间复杂度为O(1)数组简单易用使用的是连续的内存空间可以借助CPU的缓存机制预读数组中的数据提高访问效率。
缺点
插入、删除操作低效 O(n)因为需要进行数据迁移。数组大小固定一经声明就要占用整块连续内存空间。如果声明的数组过大系统可能没有足够的连续内存空间分配导致“内存不足”如果声明的数组过小则可能出现不够用的情况需要申请更大的内存空间把原数据拷贝进去非常耗时。
数组和链表的区别
数组支持随机访问适合查找根据下标随机访问的时间复杂度为O(n)链表适合插入、删除时间复杂度O(1)
时间复杂度
Access: O(1)Insert: 平均 O(n)Delete: 平均 O(n)
链表 Linked List 是由许多相同数据类型的数据项按特定顺序排列而成的线性表。 特点内存不连续各个数据项在计算机内存中的位置是不连续且随机存放的链表通过指针将一组零散的内存块串联在一起。 优点
数据的插入或删除都相当方便有新数据加入就向系统申请一块内存空间而数据被删除后就可以把这块内存空间还给系统加入或删除都不需要移动大量的数据支持动态扩容。
缺点
设计数据结构时较为麻烦并且在查找数据时无法像静态数据那样可随机读取数据必须按顺序查找到该数据为止。
时间复杂度
space O(n)prepend O(1)append O(1)lookup O(1)insert O(1)delete O(1)
单向链表 由数据字段和指针两个元素组成 单向链表只有一个方向节点只有一个后继指针next指向后面的节点。 “单向链表”中第一个节点是“链表头指针”指向最后一个节点的指针设为None表示它是“链表尾”不指向任何地方。 双向链表 双向链表支持两个方向每个节点不止有一个后继指针next指向后面的节点还有一个前驱指针prev指向前面的节点。 优势支持O(1)时间复杂度的情况下找到前驱节点双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。 缺点占用更多的内存空间空间换时间数据结构复杂。 循环链表 是一种特殊的单链表单链表的尾节点指针指向空地址而循环链表的尾节点指针指向链表的头节点。 和单链表相比循环链表的优点是从链尾到链头比较方便循环链表适合处理具有环型结构特点的数据。 双向循环链表
堆栈 Stack 是一组相同数据类型的组合具有“后进先出”的特征所有的操作均在堆栈结构的顶端进行。 抽象型数据结构 First In Last Out (FILO) Array or Linked List 特性 只能从堆栈的顶端存取数据数据的存取符合“后进先出”的原则 基本运算 基本运算说明create创建一个空堆栈push把数据压入堆栈顶端并返回新堆栈pop从堆栈顶端弹出数据并返回新堆栈isEmpty判断堆栈是否为空栈是则返回true不是则返回falsefull判断堆栈是否已满是则返回true不是则返回false
队列 Queue 是一种“先进先出”的数据结构和堆栈一样都是一种有序线性表的抽象数据类型。 抽象数据结构 First In First Out (FIFO) Array or Linked List 特性 具有先进先出的特性拥有加入与删除两种基本操作而且使用from与rear两个指针来分别指向队列的前端与末尾。 基本操作 基本操作说明create创建空队列add将新数据加入队列的末尾返回新队列delete删除队列前端的数据返回新队列front返回队列前端的值empty若队列为空返回“真”否则返回“假”
优先队列 Priority Queue 是一种不必遵守队列特性FIFO先进先出的有序线性表其中的每一个元素都赋予一个优先级加入元素时可任意加入但有最高优先级者则最先输出。 哈希表 Hash Table 是一种存储记录的连续内存通过哈希函数的应用可以快速存取与查找数据。基本上所谓哈希法就是将本身的键值通过特定的数学函数运算或使用其他方法转换成相对应的数据存储地址。 bucket桶哈希表中存储数据的位置每一个位置对应到唯一的一个地址bucket addressslot(槽)每一个记录中可能包含好几个字段而slot指的是“桶”中的字段collision碰撞两项不同的数据经过哈希函数运算后对应到相同的地址。溢出如果数据经过哈希函数运算后所对应到的bucket已满就会使bucket发生溢出。哈希表存储记录的连续内存。哈希表示一种类似数据表的索引表格可分为n个bucket每个bucket又可分为m个slot。同义词两个标识符I1和I2经哈希函数运算后所得的数值相同即f(I1)f(I2)就称I1与I2对于f这个哈希函数是同义词。加载密度指标识符的使用数量除以哈希表内槽的总数完美哈希没有碰撞也没有溢出的哈希函数
哈希函数设计原则
降低碰撞和溢出的产生哈希函数不宜过于复杂越容易计算越佳尽量把文字的键值转换成数字的键值以利于哈希函数的运算所设计的哈希函数计算得到的值尽量能均匀地分布在每一个桶中不要太过于集中在某些桶内这样就可以降低碰撞并减少溢出的处理。
树、⼆叉树 Linked List 就是特殊化的 Tree Tree 就是特殊化的 Graph 度数每个节点所有子树的个数 层数树的层数 高度树的最大层数 树叶或终端节点度数为零的节点 父节点每一个节点有连接的上一层节点父节点 子节点每一个节点有连接的下一层节点子节点 祖先指从树根到该节点路径上所包含的节点 子孙该节点往下追溯子树中的任意节点 兄弟节点有共同父节点的节点为兄弟节点 非终端节点树叶以外的节点 同代在同一颗中具有相同层数的节点 森林n棵n0互斥树的集合 满二叉树 所有叶节点都在最底层的完全二叉树 完全二叉树 对于一颗二叉树假设深度为d除了d层外其它各层的节点数均已达到最大值并且第d层所有节点从左向右连续紧密排列 二叉排序树 任何一个节点所有左边的值都会比此节点小所有右边的值都会比此节点大 平衡二叉树 当且仅当任何节点的两棵子树的高度差不大于1的二叉树
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fR51LgSH-1677826933387)(C:\Users\F2849526\記事本\数据结构与算法\algorithm-1-master\algorithm-1-master\tree)]
⼆叉搜索树 若任意节点的左子树不空则左子树上所有结点的值均小于它的根结点的值若任意节点的右子树不空则右子树上所有结点的值均大于它的根结点的值任意节点的左、右子树也分别为二叉查找树。 二叉树遍历 前序(Pre-order)根-左-右中序(In-order)左-根-右后序(Post-order)左-右-根 常见算法
递归 Recursion [rɪˈkɜːrʒn] 定义一个函数或子程序是由自身所定义或调用的。 满足两个条件 一个可以反复执行的递归过程一个可以离开递归执行的出口。 求解n
def factorial(n):if n 0: # 离开递归的终止条件return 1else:result n * factorial(n - 1): # 反复执行的递归过程return result斐波那契额数列的求解
# 数列的第0项是0、第1项是1之后的各项的值是由前面两项的值相加的结果。
def fib(n):if n 0:return 0elif n 1 or n 2:return 1else:return fib(n - 1) fib(n - 2)分治 Divde Conquer [ˈkɑːŋkər] 核心思想是将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题以便各个击破即“分而治之”。 任何一个可以用程序求解的问题所需的计算时间都与其规模有关问题的规模越小越容易直接求解。分割问题也是遇到大问题的解决方式可以使子问题规模不断缩小直到这些子问题足够简单到可以解决最后再将各子问题的解合并得到原问题的最终解答。 应用场景 快速排序递归算法大整数乘法 迭代法 指无法使用公式一次求解而需要使用迭代如用循环去重复执行程序代码的某些部分来得到答案。 使用for循环来设计一个计算1 ~ n阶乘的递归程序
sum 1
n int(input(请输入n))
for i in range(0, n 1):for j in range(i, 0, -1):sum * jprint(%d! %3d % (i, sum))sum 1枚举法 核心思想是列举所有的可能。根据问题要求逐一列举问题的解答或者为了便于解决问题把问题分为不重复、不遗漏的有限种情况逐一列举各种情况并加以解决最终达到解决整个问题的目的。 列出1到500之间所有5的倍数整数
for num in range(1, 501):if num % 5 0:print(%d 是5的倍数 % num)回溯法 也是枚举法中的一种对于某些问题而言回溯法是一种可以找出所有或一部分解的一般性算法同时避免枚举不正确的数值。一旦发现不正确的数值就不在递归到下一层而是回溯到上一层以节省时间是一种走不通就退回再走的方式。 应用场景在搜索过程中寻找问题的解当发现不满足求解条件时就回溯返回尝试别的路径避免无效搜索。 贪⼼算法Greedy Algorithms) 贪心法又称贪婪算法方法是从某一起点开始在每一个解决问题步骤中使用贪心原则即采取在当前状态下最有利或最优化的选择不断地改进该解答持续在每一步骤中选择最佳的方法并且逐步逼近给定的目标当达到某一步骤不能再继续前进时算法就停止就是尽可能块地求得更好的解。 适用 Greedy 的场景简单地说问题能够分解成子问题来解决子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。 应用场景 找出图的最小生成树MST最短路径哈夫曼编码 贪心算法与动态规划的不同在于它对每个子问题的解决⽅案都做出选择不能回退。动态规划则会保存以前的运算结果并根据以前的结果对当前进行行选择有回退功能。 广度优先搜索(Breadth-First-Search)
def BFS(graph, start, end):queue []queue.append([start])visited.add(start)while queue:node queue.pop()visited.add(node)process(node)nodes generate_related_nodes(node)queue.push(nodes)# other procession work...深度优先搜索(Depth-First-Search) 递归写法 visited set()
def dfs(node, visited):visited.add(node)# process current node here....for next_node in node.children():if not next_node in visited:dfs(next_node, visited)非递归写法 def DFS(self, tree):if tree.root is None:return []visited, stack [], [tree.root]while stack:node stack.pop()nodes generate_related_nodes(node)stack.push(nodes)# other processing work...剪枝
⼆分查找Binary Search) Sorted单调递增或者递减Bounded存在上下界Accessible by index能够通过索引访问 字典树Trie)
Trie 树的数据结构 Trie树即字典树又称单词查找树或键树是一种树形结构是一种哈希树的变种。典型应用是用于统计和排序大量的字符串但不仅限于字符串所以经常被搜索引擎系统用于⽂本词频统计。 它的优点是最大限度地减少无谓的字符串比较查询效率比哈希表高。 Trie 树的核⼼思想 Trie的核⼼思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的⽬的。 Trie 树的基本性质 根节点不包含字符除根节点外每一个节点都只包含一个字符。从根节点到某一节点路径上经过的字符连接起来为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。 位运算的运⽤Bitwise operations)
动态规划Dynamic Programming) 递归记忆化 — 递推状态的定义opt[n], dp[n], fib[n]状态转移⽅程opt[n] best_of(opt[n-1], opt[n-2], …)最优子结构 类似于分治法用于研究多个阶段决策过程的优化过程与求得一个问题的最佳解。 动态规划的主要做法如果一个问题答案与子问题相关的话就能大问题拆解成各个小问题其中与分治法最大不同的地方是可以让每一个子问题的答案被存储起来以供下次求解时直接取用。这样的做法不但能减少再次计算的时间并可将这些解组合成大问题的解答故而使用动态规划可以解决重复计算的问题。 求解斐波那契数列的解
output [None] * 1000 # fibonacci的暂存区def Fibonacci(n):result output[n]if result None:if n 0:result 0elif n 1:result 1else:result Fibonacci(n - 1) Fibonacci(n - 2)output[n] resultreturn result图 图是由“定点”和“边”所组成的集合通常用G(V, E)来表示其中V 是所有定点所组成的集合而E代表所有变所组成的集合。 无向图 是一种变没有方向的图即同边的两个定点没有次序关系。 V {A, B, C, E} E {(A, B), (A, E), (B, C), (B, D), (C, D), (C, E), (D, E)} 有向图 是一种每一条边都可使用有序对V1, V2来表示的图 并且V1, V2与V2, V1是表示两个方向不同的边而所谓V1, V2是指V1为尾端指向为头部的V2 加权图
