广东海外建设监理有限公司官方网站,河北建设工程信息网登陆,固原建设厅官方网站,google的网站优化工具前言
问题解决技巧#xff1a;分而治之 / 动态规划#xff1b;贪婪算法书目#xff1a;Grokking algorithms: an illustrated guide for programmers and other curious people中文名称#xff1a;《算法图解——像小说一样有趣的算法入门书》
1 算法简介
二分查找…前言
问题解决技巧分而治之 / 动态规划贪婪算法书目Grokking algorithms: an illustrated guide for programmers and other curious people中文名称《算法图解——像小说一样有趣的算法入门书》
1 算法简介
二分查找输入是一个有序的元素列表运行时间线性时间对数时间大O表示法算法有多快指出了算法需要执行的操作数指出了最糟情况下的运行时间 O(log n)O(n)O(n * log n)O(n 2 )O(n!)
2 选择排序
数组和链表 链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址从而使一系列随机的内存地址串在一起。数组的读取速度更快支持随机访问数组的元素都在一起。 数组的读取速度很快。链表的插入和删除速度很快。
3 递归
递归只是让解决方案更清晰并没有性能上的优势。实际上在有些情况下使用循环的性能更好。基线条件base case和递归条件recursive case。递归条件指的是函数调用自己而基线条件则指的是函数不再调用自己从而避免形成无限循环。调用栈栈有两种操作压入和弹出。调用栈可能很长这将占用大量的内存。调用另一个函数时当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。
4 快速排序 分而治之divide and conquerDC (1) 找出基线条件这种条件必须尽可能简单。 (2) 不断将问题分解或者说缩小规模直到符合基线条件。 编写涉及数组的递归函数时基线条件通常是数组为空或只包含一个元素。 平均情况和最糟情况
5 散列表
散列函数是这样的函数即无论你给它什么数据它都还你一个数字。将输入映射到数字散列表hash table——字典避免冲突需要有 较低的填装因子良好的散列函数。
6 广度优先搜索
图模拟一组连接。图由节点node和边edge组成。队列队列是一种先进先出First In First OutFIFO的数据结构而栈是一种后进先出Last In First OutLIFO的数据结构。from collections import deque你需要按加入顺序检查搜索列表中的人否则找到的就不是最短路径因此搜索列表必须是队列。对于检查过的人务必不要再去检查否则可能导致无限循环。
7 狄克斯特拉算法
Dijkstra’s algorithm总权重最小的路径。带权重的图称为加权图weighted graph不带权重的图称为非加权图unweighted graph。狄克斯特拉算法只适用于有向无环图directed acyclic graphDAG。如果有负权边就不能使用狄克斯特拉算法。贝尔曼-福德算法Bellman-Ford algorithm。infinity float(“inf”)
8 贪婪算法
每步都选择局部最优解教室调度问题背包问题集合覆盖问题旅行商问题很多非常聪明的人都认为根本不可能编写出可快速解决这些问题的算法。NP-complete没办法判断问题是不是NP完全问题 元素较少时算法的运行速度非常快但随着元素数量的增加速度会变得非常慢。如果问题涉及集合如广播台集合且难以解决它可能就是NP完全问题。如果问题涉及序列如旅行商问题中的城市序列且难以解决它可能就是NP完全问题。
9 动态规划
动态规划先解决子问题再逐步解决大问题。在背包问题中你必须在背包容量给定的情况下偷到价值最高的商品。在问题可分解为彼此独立且离散的子问题时就可使用动态规划来解决。每种动态规划解决方案都涉及网格。单元格中的值通常就是你要优化的值。费曼算法Feynman algorithm (1) 将问题写下来。(2) 好好思考。(3) 将答案写下来。 每个单元格都是一个子问题因此你需要考虑如何将问题分解为子问题。没有放之四海皆准的计算动态规划解决方案的公式。
10 K最近邻算法
KNN用于分类和回归需要考虑最近的邻居。分类就是编组。回归就是预测结果如数字。
11 10种算法
树二叉查找树binary search tree左子节点的值都比它小而右子节点的值都比它大。反向索引
