找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

【算法】关于算法-终结篇【誊写】

admin 2019-9-9 07:16 121人围观 C++相关

原文发表于[2018-07-02]

刚刚看完两场世界杯16强赛, 都是点球大战, 现在是凌晨5点, 但是异常清醒, 昨天写的关于算法的文章, 实在是开会无聊, 打发时间写的, 限于手机码字, 觉得很多点有遗漏, 所以现在把一些我认为算法的精髓, 以及很有意思的例子和大家share一下.

昨天主要说的什么是算法, 那今天说说算法的精髓, 我认为就是分而治之的思想(divide and conquer), 简单的说就是解决一个k规模的问题很难, 那我可以把这个问题分成1规模和k-1规模的两个问题分开解决, 如果k-1规模我还是直接解决不了, 则继续分成1和k-2,一直分解到我能解决的规模.这简直是解决计算机甚至生活中一切问题的精髓. 那伴随这一精髓就有两种表现, 一种我认为是自上而下的分解:递归;另一种是自下而上的堆砌:迭代.

分开解释,比如求5!, 如果按照递归的思想, 5! = 5*4! = 5*4*3! - 5*4*3*2! = 5*4*3*2*1!,终于1!=1,相当于终于分解到计算机能求出来的阶乘了.从大问题一点点变成小问题,既递归.

同样是求5!, 如果是迭代的思想, 就是1! = 1, 2! = 2*1!, 依次类推直到n=5时,求出5的阶乘.那如此看来, 迭代和递归没什么区别啊(我这么认为了好久),但是如果把例子从求5!换成另一个很复杂的问题的话呢,这里就直接上我在实践过后的结论了: 如果一个问题可以通过很明确的数学表达式概括出k级规模和k-1级规模的关系,最好用迭代.譬如说求斐波那切数列的第100项值(1,1,2,3,5,8,13....每一项为前两项之和), 如果使用迭代的话经过98次计算即可就得结果,但是如果使用递归呢,计算次数异常庞大(用2016年产的mac运行用递归算法求解的代码, 一顿饭的时间都没算出结果....),这是因为递归算法在这个例子中进行了大量的重复运算,举例来说, 为了算f100(fn来指代求第n个斐波那切数),就要先计算f99和f98, 为了计算f99就要计算f98和f97,发现了么, 刚刚到这里,就要计算两次f98, 而且这个递归越往下进行,重复计算的次数呈指数增长, f100,想想吧,就算是2的100次方都是天文数字了.

所以,能用迭代算法就尽量不要用递归算法,虽然有时候递归算法更容易被人类所理解(但是有时候有些问题只能用递归算法求解)

哪怕递归算法和迭代算法都使用相等的计算步骤得出结果,递归算法还有一个问题, 那就是因为递归算法求出结果依赖于所有小规模问题求出结果,既要想求得5!,必须先求得4!.....必须先求得1!,但是在代码层面上,递归算法的实现一般都是通过方法在内部调用自己实现的.所以就造成了方法执行时的嵌套,如果递归规模很大,每一层方法都是在内存的调用栈中保存的,就会消耗大量的内存资源.

那之前说了数组和链表两种数据结构, 现在再来说说散列表.

有关数组其实还要多说一点,之前说数组的读,存效率高,其实有一点没说, 就是打个比喻, 数组就好像电影院一排连续的座位, 你有5个人要去看电影, 那就预定5个连续的座位(开辟5个连续的内存空间), 这没什么问题, 但是有个问题,如果这个时候又来了一个人,怎么办呢,恰巧这5个座位的两端都坐了别人, 如果还要保证数组结构, 此时就只能再找一个6个连续座位的空间,那再来一个人呢,所以一般在创建数组时,都会传一个数组规模, 这时候, 内存中会开辟一块传入规模两倍的连续内存空间,(你预定5个连续座位,电影院会给你留10个连续座位), 但是留的再多,都可能不够,所以每次数组扩容时,都会扩容为当前容量的两倍,所以每次扩容都伴随着数组元素的移动,如果不扩容,可能又会造成内存空间的浪费(留了10个,只来了5个人,剩下的5个座位别人也不能做,就浪费了),但是这只说了皮毛, 要再想深入了解,就要看计算机原理了.

接着说散列表,散列表我个人的理解就是通过散列函数封装的数组, 解释一下, 数组查找数据很快,只要知道下标就可以以常数步骤完成查找数据, 但是, 10000个数据我怎么能记得住我想查的数据在哪个下标呢, 就好比查字典,我要是能记住每个单词在哪一页我确实可以一步到位, 但我要能记住每个单词在哪一页我还用得着查字典么.所以这是就需要一个函数, 这个函数就干一件事, 就是我说一个单词, 他告诉我单词在哪一页,但是单词本质上还是存在数组里的, 说白了,原来通过下标访问数组,现在通过我们自己定义的关键字访问数组,既这里的我想查的单词,所以散列表实现的关键,就是散列函数的实现, 散列函数实现的关键就是要尽可能的把关键字转化为随机且分布均匀的数组下标, 比如说按单词首字母分类的散列函数就不是一个好的散列函数,a=1,b=2...z=26,那数组规模要是10000, 真正有效可用的位置其实就是前26个,因为按照散列函数来看, 后面所有的下标值都不会被映射到.所以好的散列函数要尽可能多(而不重复)的利用数组空间, 将每一个元素映射到不同的下标中,且唯一,不能说这次apple被映射到下标为2的空间, 下次查找的时候又告诉我他在下标为9998的空间中.

如果上面说的理解了, 很快就会出现问题,那就是,数组空间有限,再牛逼的函数也不可能应对无限的输入可能啊, 总会出现两个关键字经过散列函数的运算得到相同的下标值,那这时候怎么办呢.首先说一点,这种情况的专业用语叫做冲突, 再明确一个概念,散列表这种数据结构,冲突不可能避免,只能减少(通过优化散列函数),那冲突出现以后怎么解决呢, 就是在冲突所在位置的空间中存放一个链表,把应该放在这个空间的多个元素存放在链表中.理解不了也无所谓,因为散列表这种数据结构在java中就是hashmap, swift就是字典, 语言已经给我们都实现好了, 我们只管用就行了,使用过程中,你根本不知道有没有发生冲突, 发生了是怎么解决的.

那最后再说一点我觉得最有意思的,就是斐波那契查找和np完全问题,贪婪算法.

先说斐波那契查找, 斐波那契查找是对二分查找的一种优化,这里先详细说一下计算机执行二分查找的步骤,从1到9的一列数, 你问计算机8在什么位置,计算机首先拿8跟5比大小,8比5大,所以8不在下半区,同时8也不等于5,所以8可能在上半区,所以发现没有, 一次比较就能知道8在不在下半区,但是要两次比较才能知道8在不在上半区,所以看似公平的从中间比较其实不公平,因为左右两侧的运算次数不等,所以直接上结论了



截图来自:https://blog.csdn.net/lzdidiv/article/details/59784694

最后说说np完全问题,讲了这么多的算法, 终于说到这了, 这里直接上例子, 经典的商旅问题, 既一个人要去5个地方,要求设计一条最短路线.这里直接给结论了,这个计算很简单,其实就是5个元素全排列,求出每一种排列后对应的路线长度, 最后取最小值就是正解.

但是!如果这个问题的规模上升到50个地方呢,那就是50!,要是500个地方呢(大数据时代,500这个规模可一点都算不上大),很快,根据现有算法,计算这个问题的解需要的计算步骤就已经到了天文数字的级别, 这种问题, 虽然有算法可以求解,但是随着规模的增大,很快就变得"不可计算"(不是真的没法计算,是计算耗时太长,长到失去了计算的意义),这种问题就算是np完全问题, 当然,其实np完全是有定义的,可以百度, 但是你发现百度以后意义一下其实就是有限的时间算不出结果的问题.

那这种问题怎么办呢, 就只能用贪婪算法, 简单的说, 这类问题之所以没法计算就是因为我们追求完美, 要把所有的可能都计算出来求出最完美的结果, 那贪婪算法就不这么看, 贪婪算法的精髓就是, 每一步只考虑当前这一步的最优解,你要去5个地方,好!我先看哪一个地方离你最近就先去哪个地方,到了这个地方再看剩下的四个地方哪个离你最近就去哪个地方,以此类推,以每一步的最优解相加进而求得贪婪算法认为的全局最优解(其实也是生活经验的总结, 不知道能干啥的时候就先干能干的好的).

至此,我觉得差不多把我对算法的所有可以用简单语言表达的部分都写出来了.分享一下我的学习路线吧.算法入门是通过听清华大学邓俊辉老师的视频公开课完成的,这个课讲得真的是特别好, 全程用伪代码授课.但是自以为算法很简单的我买了一本超级厚的算法导论,看过的人应该都懂,那本书看的我真是虐的不行不行的,一度让我对算法甚至编程失去信心,最后就是前天闲来无事刷的一本Aditya Bhargava写的算法图解,这书写的确实挺有意思, 而且完全是面向毫无基础的人.总结一下,我觉得没写过代码的人看这本算法图解入门挺好的, 写过代码的可以直接看邓俊辉老师的公开课, 最后, 认为自己对算法数据结构以及各种高等数学都很有把握的人, 去读算法导论吧!!!


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:CreatedByEdison,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......