【算法】算法图解笔记_算法简介

tomlingtm 发布于2019-07-31 10:10 / 1281人阅读

摘要：在本书中你将学习比较不同算法的优缺点该使用合并排序算法还是快速排序算法或者该使用数组还是链表。这样的算法包括快速排序一种速度较快的排序算法。

在读《算法图解》这本书，这本书有两个优点：

手绘风格的图，看着很让人“入戏”；

算法采用Python语言描述，能更好的表达算法思想。

关于算法的学习有两点心得：

算法思想最重要，理解了思想，算法是很容易写出来的，所以尽量不要把过多精力放在细节上。
比如，本书的快速排序，使用了列表推导式，很简单就把算法的思想描述了出来。相比而言，某些使用C语言的书籍给出的版本则比较难懂，归其原因是因为太突出细节了。细节不是不重要，而是我们要首先把算法能更好地理解，下一步才是实现和优化。

某些情况下递归比迭代更容易表达算法
递归是描述性的，侧重了对算法性质的表达；而迭代更侧重算法实现，往往掺杂了太多的实现细节。所以，我同时用Haskell给出递归版本的算法描述。

好了，开始。

引言

算法是一组完成任务的指令。任何代码片段都可视为算法。
[注意：该书对算法的定义与通行的定义不同，通行的定义要求算法应该具有有穷性，即算法必须能在执行有限个步骤之后终止，否则算法是没有意义的。]

在本书中,你将学习比较不同算法的优缺点:该使用合并排序算法还是快速排序算法,或者该使用数组还是链表。仅仅改用不同的数据结构就可能让结果大不相同。

二分查找（binary search）

其输入是一个有序的元素列表;查找的元素包含在列表中,二分查找返回其位置;否则返回 Nothing。
一般而言,对于包含n个元素的列表,用二分查找最多需要log2n步。

Python版本：

def binary_search(list, item):
    low = 0
    high = len(list)—1
    
    while low <= high:
        mid = (low + high)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

Haskell版本：使用了Vector，因为标准库的列表是单链表，不支持随机访问。

import qualified Data.Vector as V

binarySearch :: (Ord a)=>  V.Vector a -> Int -> Int -> a -> Maybe Int
binarySearch vec low high e
          | low > high = Nothing
          | vec V.! mid < e = binarySearch vec (mid+1) high e
          | vec V.! mid > e = binarySearch vec low (mid-1) e
          | otherwise = Just mid
          where
              mid = low + ((high-low) `div` 2)

大 O 表示法

仅知道算法需要多长时间才能运行完毕还不够,还需知道运行时间如何随列表增长而增加。

算法的运行时间以不同的速度增加

算法的速度指的并非时间,而是操作数的增速。谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。大 O 表示法让你能够比较操作数,它指出了算法运行时间的增速。

大 O 表示法指出了最糟情况下的运行时间

这是一个保证——如，简单查找的运行时间不可能超过O(n)。

一些常见的大 O 运行时间

 O(log n),也叫对数时间,这样的算法包括二分查找。
 O(n),也叫线性时间,这样的算法包括简单查找。
 O(n * log n),这样的算法包括快速排序——一种速度较快的排序算法。
 O(n2),这样的算法包括选择排序——一种速度较慢的排序算法。
 O(n!),这样的算法包括旅行商问题的解决方案——一种非常慢的算法

旅行商问题

旅行商要前往n个城市,同时要确保旅程最短，时间复杂度：O(n!)。

请关注我的公众号哦。

GPU云服务器云服务器排序算法图解云计算_算法数据结构算法算法字符串处理算法匹配算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43380.html

【算法】算法图解笔记_递归

递归是个有意思的概念，正如在前面所说，递归能让算法的可读性大大提高，而且通常要比使用循环结构更能写出准确的算法。这本书形象引入了递归，并没有太深入，所以我进行了一点添油加醋。递归概念递归其实就是自己调用自己。可以从多种维度对递归分类，我见过的最常见的分类：直接递归自己直接调用自己。如： --haskell length :: [a] -> Int length [] = 0 length...

tomlingtm 2019-07-31 10:12 评论0 收藏0
【算法】算法图解笔记_选择排序

摘要：选择排序是下一章将介绍的快速排序的基石。需要存储多项数据时有两种基本方式数组和链表。但它们并非都适用于所有的情形因此知道它们的差别很重要。选择排序是一种灵巧的算法但其速度不是很快。选择排序是下一章将介绍的快速排序的基石。内存的工作原理计算机就像是很多抽屉的集合体,每个抽屉都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...

mylxsw 2019-07-31 10:12 评论0 收藏0
【算法】算法图解笔记_广度优先搜索

摘要：解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由年在如何从迷宫中寻找出路这一问题中提出。广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索解决问题。你经常需要解决最短路径问题(shorterst-path problem)。解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由Edward F. Moore 1959年在如何从迷宫中寻找出路这一...

sanyang 2019-07-31 10:18 评论0 收藏0
【算法】算法图解笔记_快速排序

摘要：再谈大表示法快速排序的独特之处在于其速度取决于选择的基准值。在平均情况下快速排序的运行时间为在最糟情况下退化为。快速排序和合并排序的算法速度分别表示为和，是算法所需的固定时间量被称为常量。分而治之分而治之(divide and conquer,D&C)是一种著名的递归式问题解决方法。只能解决一种问题的算法毕竟用处有限,而D&C提供了解决问题的思路,是另一个可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 评论0 收藏0