我的书签
添加书签
移除书签数据结构和算法
- 算法：解决问题的方法和步骤
- 评价算法的好坏：渐近时间复杂度和渐近空间复杂度。
- 渐近时间复杂度的大O标记：
- 常量时间复杂度 - 布隆过滤器 / 哈希存储
- 对数时间复杂度 - 折半查找（二分查找）
- 线性时间复杂度 - 顺序查找 / 计数排序
- 对数线性时间复杂度 - 高级排序算法（归并排序、快速排序）
- 平方时间复杂度 - 简单排序算法（选择排序、插入排序、冒泡排序）
- 立方时间复杂度 - Floyd算法 / 矩阵乘法运算
- 几何级数时间复杂度 - 汉诺塔
- 阶乘时间复杂度 - 旅行经销商问题 - NPC
排序算法（选择、冒泡和归并）和查找算法（顺序和折半）
def select_sort(items, comp=lambda x, y: x < y):“””简单选择排序”””items = items[:]for i in range(len(items) - 1):min_index = ifor j in range(i + 1, len(items)):if comp(items[j], items[min_index]):min_index = jitems[i], items[min_index] = items[min_index], items[i]return items
def bubble_sort(items, comp=lambda x, y: x > y):“””冒泡排序”””items = items[:]for i in range(len(items) - 1):swapped = Falsefor j in range(len(items) - 1 - i):if comp(items[j], items[j + 1]):items[j], items[j + 1] = items[j + 1], items[j]swapped = Trueif not swapped:breakreturn items
def bubble_sort(items, comp=lambda x, y: x > y):“””搅拌排序(冒泡排序升级版)”””items = items[:]for i in range(len(items) - 1):swapped = Falsefor j in range(len(items) - 1 - i):if comp(items[j], items[j + 1]):items[j], items[j + 1] = items[j + 1], items[j]swapped = Trueif swapped:swapped = Falsefor j in range(len(items) - 2 - i, i, -1):if comp(items[j - 1], items[j]):items[j], items[j - 1] = items[j - 1], items[j]swapped = Trueif not swapped:breakreturn items
```Python def merge(items1, items2, comp=lambda x, y: x < y):
“””合并(将两个有序的列表合并成一个有序的列表)”””items = []index1, index2 = 0, 0while index1 < len(items1) and index2 < len(items2):if comp(items1[index1], items2[index2]):items.append(items1[index1])index1 += 1else:items.append(items2[index2])index2 += 1items += items1[index1:]items += items2[index2:]return items
def merge_sort(items, comp=lambda x, y: x < y):
return _merge_sort(list(items), comp)</p>
def _merge_sort(items, comp):
“””归并排序”””if len(items) < 2:return itemsmid = len(items) // 2left = _merge_sort(items[:mid], comp)right = _merge_sort(items[mid:], comp)return merge(left, right, comp)</p>
Python</span></code></li><li class="L2"><code><span class="str"> def seq_search(items, key):</span></code></li><li class="L3"><code><span class="str"> """顺序查找"""</span></code></li><li class="L4"><code><span class="str"> for index, item in enumerate(items):</span></code></li><li class="L5"><code><span class="str"> if item == key:</span></code></li><li class="L6"><code><span class="str"> return index</span></code></li><li class="L7"><code><span class="str"> return -1</span></code></li></ol></pre><pre class="prettyprint linenums prettyprinted" style=""><button class="btn btn-danger btn-sm btn-copy"><i class="fa fa-copy"></i> 复制代码</button><ol class="linenums"><li class="L0"><code class="lang-Python"><span class="pln"> </span><span class="kwd">def</span><span class="pln"> bin_search</span><span class="pun">(</span><span class="pln">items</span><span class="pun">,</span><span class="pln"> key</span><span class="pun">):</span></code></li><li class="L1"><code class="lang-Python"><span class="pln"> </span><span class="str">"""折半查找"""</span></code></li><li class="L2"><code class="lang-Python"><span class="pln"> start</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">end</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">,</span><span class="pln"> len</span><span class="pun">(</span><span class="pln">items</span><span class="pun">)</span><span class="pln"> </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span></code></li><li class="L3"><code class="lang-Python"><span class="pln"> </span><span class="kwd">while</span><span class="pln"> start </span><span class="pun"><=</span><span class="pln"> </span><span class="kwd">end</span><span class="pun">:</span></code></li><li class="L4"><code class="lang-Python"><span class="pln"> mid </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">start </span><span class="pun">+</span><span class="pln"> </span><span class="kwd">end</span><span class="pun">)</span><span class="pln"> </span><span class="com">// 2</span></code></li><li class="L5"><code class="lang-Python"><span class="pln"> </span><span class="kwd">if</span><span class="pln"> key </span><span class="pun">></span><span class="pln"> items</span><span class="pun">[</span><span class="pln">mid</span><span class="pun">]:</span></code></li><li class="L6"><code class="lang-Python"><span class="pln"> start </span><span class="pun">=</span><span class="pln"> mid </span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span></code></li><li class="L7"><code class="lang-Python"><span class="pln"> </span><span class="kwd">elif</span><span class="pln"> key </span><span class="pun"><</span><span class="pln"> items</span><span class="pun">[</span><span class="pln">mid</span><span class="pun">]:</span></code></li><li class="L8"><code class="lang-Python"><span class="pln"> </span><span class="kwd">end</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> mid </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span></code></li><li class="L9"><code class="lang-Python"><span class="pln"> </span><span class="kwd">else</span><span class="pun">:</span></code></li><li class="L0"><code class="lang-Python"><span class="pln"> </span><span class="kwd">return</span><span class="pln"> mid</span></code></li><li class="L1"><code class="lang-Python"><span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="pun">-</span><span class="lit">1</span></code></li></ol></pre> <ul> <li><p>常用算法：</p> <ul> <li>穷举法 - 又称为暴力破解法，对所有的可能性进行验证，直到找到正确答案。</li><li>贪婪法 - 在对问题求解时，总是做出在当前看来</li><li>最好的选择，不追求最优解，快速找到满意解。</li><li>分治法 - 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到可以直接求解的程度，最后将子问题的解进行合并得到原问题的解。</li><li>回溯法 - 回溯法又称为试探法，按选优条件向前搜索，当搜索到某一步发现原先选择并不优或达不到目标时，就退回一步重新选择。</li><li>动态规划 - 基本思想也是将待求解问题分解成若干个子问题，先求解并保存这些子问题的解，避免产生大量的重复运算。</li></ul> <p>穷举法例子：百钱百鸡和五人分鱼。</p> <pre class="prettyprint linenums prettyprinted" style=""><button class="btn btn-danger btn-sm btn-copy"><i class="fa fa-copy"></i> 复制代码</button><ol class="linenums"><li class="L0"><code class="lang-Python"><span class="com"># 公鸡5元一只 母鸡3元一只 小鸡1元三只</span></code></li><li class="L1"><code class="lang-Python"><span class="com"># 用100元买100只鸡 问公鸡/母鸡/小鸡各多少只</span></code></li><li class="L2"><code class="lang-Python"><span class="kwd">for</span><span class="pln"> x </span><span class="kwd">in</span><span class="pln"> range</span><span class="pun">(</span><span class="lit">20</span><span class="pun">):</span></code></li><li class="L3"><code class="lang-Python"><span class="pln"> </span><span class="kwd">for</span><span class="pln"> y </span><span class="kwd">in</span><span class="pln"> range</span><span class="pun">(</span><span class="lit">33</span><span class="pun">):</span></code></li><li class="L4"><code class="lang-Python"><span class="pln"> z </span><span class="pun">=</span><span class="pln"> </span><span class="lit">100</span><span class="pln"> </span><span class="pun">-</span><span class="pln"> x </span><span class="pun">-</span><span class="pln"> y</span></code></li><li class="L5"><code class="lang-Python"><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="pun">*</span><span class="pln"> x </span><span class="pun">+</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="pun">*</span><span class="pln"> y </span><span class="pun">+</span><span class="pln"> z </span><span class="com">// 3 == 100 and z % 3 == 0:</span></code></li><li class="L6"><code class="lang-Python"><span class="pln"> </span><span class="kwd">print</span><span class="pun">(</span><span class="pln">x</span><span class="pun">,</span><span class="pln"> y</span><span class="pun">,</span><span class="pln"> z</span><span class="pun">)</span></code></li><li class="L7"><code class="lang-Python"></code></li><li class="L8"><code class="lang-Python"><span class="com"># A、B、C、D、E五人在某天夜里合伙捕鱼 最后疲惫不堪各自睡觉</span></code></li><li class="L9"><code class="lang-Python"><span class="com"># 第二天A第一个醒来 他将鱼分为5份 扔掉多余的1条 拿走自己的一份</span></code></li><li class="L0"><code class="lang-Python"><span class="com"># B第二个醒来 也将鱼分为5份 扔掉多余的1条 拿走自己的一份</span></code></li><li class="L1"><code class="lang-Python"><span class="com"># 然后C、D、E依次醒来也按同样的方式分鱼 问他们至少捕了多少条鱼</span></code></li><li class="L2"><code class="lang-Python"><span class="pln">fish </span><span class="pun">=</span><span class="pln"> </span><span class="lit">6</span></code></li><li class="L3"><code class="lang-Python"><span class="kwd">while</span><span class="pln"> </span><span class="kwd">True</span><span class="pun">:</span></code></li><li class="L4"><code class="lang-Python"><span class="pln"> total </span><span class="pun">=</span><span class="pln"> fish</span></code></li><li class="L5"><code class="lang-Python"><span class="pln"> enough </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">True</span></code></li><li class="L6"><code class="lang-Python"><span class="pln"> </span><span class="kwd">for</span><span class="pln"> _ </span><span class="kwd">in</span><span class="pln"> range</span><span class="pun">(</span><span class="lit">5</span><span class="pun">):</span></code></li><li class="L7"><code class="lang-Python"><span class="pln"> </span><span class="kwd">if</span><span class="pln"> </span><span class="pun">(</span><span class="pln">total </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">)</span><span class="pln"> </span><span class="pun">%</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> </span><span class="pun">==</span><span class="pln"> </span><span class="lit">0</span><span class="pun">:</span></code></li><li class="L8"><code class="lang-Python"><span class="pln"> total </span><span class="pun">=</span><span class="pln"> </span><span class="pun">(</span><span class="pln">total </span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pun">)</span><span class="pln"> </span><span class="com">// 5 * 4</span></code></li><li class="L9"><code class="lang-Python"><span class="pln"> </span><span class="kwd">else</span><span class="pun">:</span></code></li><li class="L0"><code class="lang-Python"><span class="pln"> enough </span><span class="pun">=</span><span class="pln"> </span><span class="kwd">False</span></code></li><li class="L1"><code class="lang-Python"><span class="pln"> </span><span class="kwd">break</span></code></li><li class="L2"><code class="lang-Python"><span class="pln"> </span><span class="kwd">if</span><span class="pln"> enough</span><span class="pun">:</span></code></li><li class="L3"><code class="lang-Python"><span class="pln"> </span><span class="kwd">print</span><span class="pun">(</span><span class="pln">fish</span><span class="pun">)</span></code></li><li class="L4"><code class="lang-Python"><span class="pln"> </span><span class="kwd">break</span></code></li><li class="L5"><code class="lang-Python"><span class="pln"> fish </span><span class="pun">+=</span><span class="pln"> </span><span class="lit">5</span></code></li></ol></pre> <p>贪婪法例子：假设小偷有一个背包，最多能装20公斤赃物，他闯入一户人家，发现如下表所示的物品。很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。</p> <p>| 名称 | 价格（美元） | 重量（kg） | | :——: | :—————: | :————: | | 电脑 | 200 | 20 | | 收音机 | 20 | 4 | | 钟 | 175 | 10 | | 花瓶 | 50 | 2 | | 书 | 10 | 1 | | 油画 | 90 | 9 |</p> <p>Python “”” 贪婪法：在对问题求解时，总是做出在当前看来是最好的选择，不追求最优解，快速找到满意解。 输入： 20 6 电脑 200 20 收音机 20 4 钟 175 10 花瓶 50 2 书 10 1 油画 90 9 “”” class Thing(object):
“””物品”””def init(self, name, price, weight):self.name = nameself.price = priceself.weight = weight@propertydef value(self):“””价格重量比”””return self.price / self.weightdef input_thing():
“””输入物品信息””” name_str, price_str, weight_str = input().split() return name_str, int(price_str), int(weight_str)</p>def main():
“””主函数””” max<em>weight, num_of_things = map(int, input().split()) all_things = [] for </em> in range(num_of_things): all_things.append(Thing(*input_thing())) all_things.sort(key=lambda x: x.value, reverse=True) total_weight = 0 total_price = 0 for thing in all_things: if total_weight + thing.weight <= max_weight: print(f’小偷拿走了{thing.name}’) total_weight += thing.weight total_price += thing.price print(f’总价值: {total_price}美元’)</p>if name == ‘main‘:
main()</p>
分治法例子：快速排序。```Python“””快速排序 - 选择枢轴对元素进行划分，左边都比枢轴小右边都比枢轴大“””def quicksort(items, comp=lambda x, y: x <= y):items = list(items)[:]_quick_sort(items, 0, len(items) - 1, comp)return itemsdef _quick_sort(items, start, end, comp):if start < end:pos = _partition(items, start, end, comp)_quick_sort(items, start, pos - 1, comp)_quick_sort(items, pos + 1, end, comp)def _partition(items, start, end, comp):pivot = items[end]i = start - 1for j in range(start, end):if comp(items[j], pivot):i += 1items[i], items[j] = items[j], items[i]items[i + 1], items[end] = items[end], items[i + 1]return i + 1回溯法例子：骑士巡逻。
“””递归回溯法：叫称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择，比较经典的问题包括骑士巡逻、八皇后和迷宫寻路等。“””import sysimport timeSIZE = 5total = 0def print_board(board):for row in board:for col in row:print(str(col).center(4), end=‘’)print()def patrol(board, row, col, step=1):if row >= 0 and row < SIZE and \col >= 0 and col < SIZE and \board[row][col] == 0:board[row][col] = stepif step == SIZE SIZE:global totaltotal += 1print(f‘第{total}种走法: ‘)print_board(board)patrol(board, row - 2, col - 1, step + 1)patrol(board, row - 1, col - 2, step + 1)patrol(board, row + 1, col - 2, step + 1)patrol(board, row + 2, col - 1, step + 1)patrol(board, row + 2, col + 1, step + 1)patrol(board, row + 1, col + 2, step + 1)patrol(board, row - 1, col + 2, step + 1)patrol(board, row - 2, col + 1, step + 1)board[row][col] = 0def main():board = [[0]SIZE forin range(SIZE)]patrol(board, SIZE - 1, SIZE - 1)if name == ‘main‘:main()动态规划例子：子列表元素之和的最大值。
说明：子列表指的是列表中索引（下标）连续的元素构成的列表；列表中的元素是int类型，可能包含正整数、0、负整数；程序输入列表中的元素，输出子列表元素求和的最大值，例如：
输入：1 -2 3 5 -3 2
输出：8
输入：0 -2 3 5 -1 2
输出：9
输入：-9 -2 -3 -5 -3
输出：-2
def main():items = list(map(int, input().split()))overall = partial = items[0]for i in range(1, len(items)):partial = max(items[i], partial + items[i])overall = max(partial, overall)print(overall)if name == ‘main‘:main()说明：这个题目最容易想到的解法是使用二重循环，但是代码的时间性能将会变得非常的糟糕。使用动态规划的思想，仅仅是多用了两个变量，就将原来$O(N^2)$复杂度的问题变成了$O(N)$。
