V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hxlx
V2EX  ›  算法

学算法有用吗?刚学会 KMP 算法,是什么层次

  •  
  •   hxlx · 2015-08-17 01:31:35 +08:00 · 12341 次点击
    这是一个创建于 3147 天前的主题,其中的信息可能已经有所发展或是发生改变。

    不会是连入门都没有吧?

    65 条回复    2016-12-20 15:56:02 +08:00
    chengzhoukun
        1
    chengzhoukun  
       2015-08-17 01:45:14 +08:00 via Android
    学了不用 并没卵用。
    Rand01ph
        2
    Rand01ph  
       2015-08-17 02:15:10 +08:00 via iPhone
    应该算入门级……才看到字符串吧
    tushiner
        3
    tushiner  
       2015-08-17 02:18:30 +08:00
    程序员用得到,而码农用不到
    gantEleCode
        4
    gantEleCode  
       2015-08-17 05:27:48 +08:00
    面试如果问到了能非常流畅的写出KMP 代码还是挺有用的。
    yyfearth
        5
    yyfearth  
       2015-08-17 05:36:41 +08:00
    KMP 是有些难度的
    但是除了面试 根本用不到
    而且就算是面试 如果一上来就 KMP 估计也没啥意义
    面试官考这个又不是考验你记忆力的
    而且估计面试官也可能搞不定 KMP

    @gantEleCode 不一定哦 只能说明是刷过题 但是还是不能体现真实能力
    除非是面试顶级大公司 这种作为基础题 刷过 KMP 也算不了什么
    em70
        6
    em70  
       2015-08-17 06:28:30 +08:00 via Android   ❤️ 1
    算法的本质是让机器像人一样思考,代替人完成任务
    ffffwh
        7
    ffffwh  
       2015-08-17 06:50:59 +08:00 via Android
    是你以为你学会了kmp的层次
    ChiangDi
        8
    ChiangDi  
       2015-08-17 07:20:34 +08:00 via Android   ❤️ 3
    你是不是看到第三章字符串了。。。
    typing
        9
    typing  
       2015-08-17 08:07:55 +08:00 via iPad
    在面试中,“会实现”是非常平凡的要求,一般会默认这一点。

    基础题目会是kmp的应用,而且题目通常不是那么浅显让你觉得kmp是可行算法。建议刷题分类选择“字符串”,而不是指明“kmp”。

    再进一步,我会问“明明两层循环为什么是线性复杂度”。

    如果你在简历中标注自己会kmp算法,以上会是一些可能的问题。

    再进一步,其他字符串算法你不能不会。没有他们之间的比较你没法明白kmp的特点。这样你用kmp不是因为它适合一个问题,而是因为你只会kmp。
    (Suffix tree/array, trie, ac automaton)

    希望这些对你后面的学习有帮助。
    surefire
        10
    surefire  
       2015-08-17 08:34:06 +08:00
    很牛逼了,我连KMP是什么都不知道
    knightdf
        11
    knightdf  
       2015-08-17 08:46:51 +08:00
    需要用到的时候再去看下不就得了。。你当被诗啊?
    vietor
        12
    vietor  
       2015-08-17 08:47:13 +08:00 via Android
    用不了10年就忘干净了
    fuxiaohei
        13
    fuxiaohei  
       2015-08-17 08:52:40 +08:00
    算法是抠细节的东西,不用很容易忘记的。。
    twistoy
        14
    twistoy  
       2015-08-17 09:16:03 +08:00
    刚看完KMP?NOIP普及组入门的实力?
    deving
        15
    deving  
       2015-08-17 09:17:08 +08:00
    除非你很熟悉这一块,不然就说都不要说,人家问道非得说一点,那就扯上一点,然后赶紧收手.kmp虽然有点难度,但是又不是什么创新创造,花点时间,一两个小时就能搞明白的,根本算不上有挑战性.
    laoyuan
        16
    laoyuan  
       2015-08-17 09:18:39 +08:00
    我认为练习算法可以锻炼思维复杂度、严谨程度,具体是否用的到就无所谓了
    fakefish
        17
    fakefish  
       2015-08-17 09:43:25 +08:00
    大一的时候学的 kmp ,当时花了很多精力理解。差不多有点理解了,觉得算法可能不太适合我,就学前端了。。
    zhengnanlee
        18
    zhengnanlee  
       2015-08-17 09:52:22 +08:00
    额。。这只是一个叫做『运算规则』的东西,并不能称作算法。貌似『算法』这个词被程序员们降低太多门槛了。
    tabris17
        19
    tabris17  
       2015-08-17 09:54:01 +08:00
    KMP 好像大学时上数据结构课时就学了

    属于然并卵的层次
    pandachow
        20
    pandachow  
       2015-08-17 10:01:00 +08:00
    KMP 只在比赛中用到,实际运行中速度并不好。同样的字符串匹配问题多用 BM 以及它的一个简化版本。
    tooweakchen
        21
    tooweakchen  
       2015-08-17 10:36:18 +08:00
    入门
    zhujinliang
        22
    zhujinliang  
       2015-08-17 11:27:33 +08:00 via iPhone
    @laoyuan 最近经常看你的直播呢
    henryon
        23
    henryon  
       2015-08-17 12:48:11 +08:00
    恭喜你加入码农的行列。。
    wph95
        24
    wph95  
       2015-08-17 12:53:54 +08:00
    KMP...信息学竞赛提高组入门等级
    zerh925
        25
    zerh925  
       2015-08-17 14:01:09 +08:00
    具体某种算法可能将来并不会用到
    但是最大的帮助是训练我们的思维能力 将来遇到类似问题能举一反三
    看到 KMP 我的第一反应是 kmplayer 因为我并不知道这个算法 我的工作中也不会用到
    但是我不否认学过这个的人或多或少还在收益
    但是也许我懂的算法也许他们不会
    术业有专攻而已
    但是某些大神 也许在造轮子时候因为知道 KMP 可以在它的基础上改造出新的东西
    这才是懂算法的真正意义吧
    大部分人和人的差距不是智力 而是努力程度和浮躁的心态
    Changxu
        26
    Changxu  
       2015-08-17 14:11:38 +08:00
    KMP ?最多是 CS 本科大二的水平
    saeba1030
        27
    saeba1030  
       2015-08-17 14:20:00 +08:00
    能写进书本的算法都是然并卵的。有用的就是你知道有哪些算法,能干什么,这样在特定场合要解决问题时可以用来就用或者举一反三
    zx120120
        28
    zx120120  
       2015-08-17 14:41:22 +08:00   ❤️ 1
    学习这些算法更多的是对思维的锻炼。
    而上手实现这些算法,则可以锻炼你对边界情况的处理能力。
    而且这些流传已久的算法大都是很美的,光是知道就会很令人高兴。

    至于这些算法对做工程而言,大多是没什么用。
    毕竟,做工程很多时候只是在机械得重复得写胶水代码罢了。

    当你想要深入这么学科里的时候,写一些比胶水代码要高神的东西的时候(诸如浏览器,编译器,数据库),算法则是不可或缺的。
    然而若是想在工程方面搞一搞的话,写点点胶水代码(诸如 HTML , JavaScript , SQL )便能有很大成就感,此时对于算法的需求并不是那么强烈,更多的是需要耐心和兴趣以及审美能力。

    总的说算法就像人们口中说的数学,写点 HTML , JS ,买点菜,势必是用不到的。但是要想钻研更深的计算机科学,算法知识是必备的。

    至于到底要不要学算法,完全取决于 LZ 想做什么。
    个人建议,不要过早的跳进 网页程序员 的大坑当中,先试试学学看,试着去干掉各大公开课网站上比较“高深”的课程,或许会发现全新的世界。
    liuchang0812
        29
    liuchang0812  
       2015-08-17 15:11:05 +08:00
    大一新生的水平
    abcdabcd987
        30
    abcdabcd987  
       2015-08-17 15:24:35 +08:00
    @Changxu
    @liuchang0812
    我觉得按照年级来评判完全没有意义呀,毕竟如果按照年级评判的话,高一高二的 OI 选手就应该掌握了呀
    zhicheng
        31
    zhicheng  
       2015-08-17 15:27:30 +08:00
    初级工程师认为写出可以工作的代码就结束了,高级工程师认为写出漂亮的代码就结束了,顶级工程师认为写出可以调试的代码才算结束。

    自己看自己在哪个层次上。
    wshcdr
        32
    wshcdr  
       2015-08-17 15:33:33 +08:00
    @yyfearth 工作里面也能用到啊,谁说只能在面试里用啊
    JointLock
        33
    JointLock  
       2015-08-17 15:38:14 +08:00
    自学算法的中小学生?可看清了,手上的这颗石头就是一颗未经雕琢的原石啊!
    锻炼信息学竞赛的中小学生?可沉住气,手上的这颗石头是关键时刻可以拿来一战的武器。
    高考后预习大学课程的高中毕业生?可别骄傲,虽然你已经走在大多数高考生同学们前面了。
    大学暑假来预习算法课的大学生?可别浮躁,虽然你觉得大学什么课程内容都特么一坨翔...
    大学暑假来准备面试题的准毕业生吗?可别慌,学到了就是学到了,万一面试用到了呢...
    夏天躺尸时间却想自我提高的半路子出家的程序员?可别觉得为时已晚,该走的路就是要走!!

    学习算法这是稳赚不赔的买卖,值当!
    MrEggNoodle
        34
    MrEggNoodle  
       2015-08-17 15:59:33 +08:00
    @em70 喜欢你这句概括。
    codingpp
        35
    codingpp  
       2015-08-17 16:00:38 +08:00
    无法学以致用,就没有什么卵用
    dslwind
        36
    dslwind  
       2015-08-17 16:05:43 +08:00 via Android
    kmp 至今没看懂是什么层次?
    Wangxf
        37
    Wangxf  
       2015-08-17 16:10:40 +08:00
    面试的时候有用,大学的时候老师讲过,现在忘得差不多了
    yyfearth
        38
    yyfearth  
       2015-08-17 16:16:48 +08:00
    @zx120120 工程也有构架设计这样很有学问的东西 只有比较初级的才是堆砌重复代码
    设计合理的架构 同时编写清晰可测试的代码难度 不会比学通这些算法简单

    @wshcdr 除了 C/C++做核心 /底层开发 实在很难想到需要自己写 kmp 这样的算法
    而且我记得现在已经有更好的算法来做这个事情了
    不过理解这些算法的原理 并灵活使用还是非常值得的
    liuchang0812
        39
    liuchang0812  
       2015-08-17 17:26:30 +08:00
    @abcdabcd987 以正常人为说
    wezzard
        40
    wezzard  
       2015-08-17 17:43:02 +08:00
    看了下 KMP 的文章, 5 分鐘自己用 Swift 2 擼了一個,我是設計出身,樓主自己掂量掂量……
    wezzard
        41
    wezzard  
       2015-08-17 17:45:14 +08:00
    @typing 明明两层循环为什么是线性复杂度?

    求解釋。
    wezzard
        42
    wezzard  
       2015-08-17 17:52:52 +08:00
    KMP 碰到 "CCCCCCCCCCCCCCCCCCCC" 裏面尋找 "CCCCCCCCCCCCCCCCCCCC" 怎麼辦?這好像是 worst case 啊。
    Xs0ul
        43
    Xs0ul  
       2015-08-17 17:55:00 +08:00 via Android
    @wezzard 你 5 分钟就能写出代码还不懂为什么是线性复杂度。。不知道你是怎么写的
    wezzard
        44
    wezzard  
       2015-08-17 17:56:51 +08:00
    @Xs0ul 可是我就是不知道……
    wezzard
        45
    wezzard  
       2015-08-17 18:01:40 +08:00
    @Xs0ul 我關鍵糾結爲甚麼對潛在可能子字符串進行匹配不被算入複雜度裏面。
    beordle
        46
    beordle  
       2015-08-17 18:05:47 +08:00
    @wezzard kmp 是稳定的,没有所谓最坏情况的吧....
    wezzard
        47
    wezzard  
       2015-08-17 18:11:39 +08:00
    繼續看了看文章,發現我理解錯了,這是我的實現。看了阮一峯的 blog 才找對方向。

    https://gist.github.com/WeZZard/67c3dbe3c7ead52d4f8d
    wezzard
        48
    wezzard  
       2015-08-17 18:12:06 +08:00
    @beordle 我寫錯了……
    hitmanx
        49
    hitmanx  
       2015-08-17 18:13:35 +08:00
    worst case 好像也是 O (m+n )的,以前学过,大概原理还记得,具体的细节忘了
    ant_sz
        50
    ant_sz  
       2015-08-17 18:34:46 +08:00
    国内算法好的孩子们都被 Google Facebook 这些厂挑走了。你说学算法有用没有用?
    onceyoung
        51
    onceyoung  
       2015-08-17 18:42:19 +08:00 via Android
    有句话叫书到用时方恨少,你说有用不
    TimePower
        52
    TimePower  
       2015-08-17 18:48:53 +08:00
    记得以前看过, 貌似没用过...
    Geoion
        53
    Geoion  
       2015-08-17 20:39:53 +08:00
    膜拜啊,我都不会这个东西
    wu181184
        54
    wu181184  
       2015-08-17 21:23:01 +08:00
    把 LeetCode 过一遍,面试就够用了...
    laoyuan
        55
    laoyuan  
       2015-08-17 21:37:43 +08:00
    我正在刷 LeetCode 啊啊啊,这会在斗鱼直播用 Python 刷: http://www.douyutv.com/laoyuan
    horizon
        56
    horizon  
       2015-08-17 21:46:27 +08:00
    @laoyuan 我竟然去看了。。然后关了。
    withlqs
        57
    withlqs  
       2015-08-17 22:05:32 +08:00
    其实无关水平,主要看思维

    不过硬要问的话, tourist 的小学水平吧 2333
    tldxdhz
        58
    tldxdhz  
       2015-08-17 22:16:48 +08:00
    初中生甚至小学生都有会的,信息学竞赛党
    hxlx
        59
    hxlx  
    OP
       2015-08-17 22:32:33 +08:00
    @yyfearth 面试有经历过要写算法的
    @typing 有道理啊~正在学 Manacher
    @JointLock 对...
    @zhengnanlee 算法博大精深啊。。
    @zx120120 嗯嗯,开始学起。。。
    yyfearth
        60
    yyfearth  
       2015-08-18 02:50:30 +08:00
    @hxlx 面试当然要写算法 但是重点不在于你会不会高难度的算法已经结果怎么样
    而是过程怎么样 corner case 和 异常 处理如何
    代码是否精炼 是否有坏习惯 以及对需求的沟通交流过程

    当然 如果是面 Google FB 这些算法题都是一堆一堆的
    在 corner case 和 异常处理的前提下 迅速刷完就好了
    对于他们而言 算法都是基础

    对于面试一般的公司 对于 strstr 这样的算法题
    我认为 用暴力算法然后 refine 比上来直接 kmp 要效果好
    hitmanx
        61
    hitmanx  
       2015-08-18 13:19:36 +08:00
    有道理。况且独立写一个没有 bug 的 kmp 算法的也很不容易了,更何况还在面试这种压力大、时间紧张的场合。。我觉得有点像快排,每个人掌握原理后都觉得这个写起来应该不难,但是真写出一个没有 bug 的其实不容易。之前哪个国外高校做过实验,把学生关在一个教室了,给予足够长的时间(每个人可以想用多少时间用多少时间,直到完全确认自己的是对的),但是最终没有 bug 的还是寥寥。
    cst4you
        62
    cst4you  
       2015-08-18 13:38:35 +08:00
    KMP 是什么可以吃吗
    invite
        63
    invite  
       2015-08-18 14:48:31 +08:00
    厉害的,我还停留在 KMP 播放器的阶段。
    sincc
        64
    sincc  
       2015-08-19 09:09:25 +08:00
    如果什么东西都要用 “学了有没有用“ 来判定,那你就不适合在这个世界生活了。。。算法是对思维很好的锻炼,如果学了算法后,用代码实现,或者去参加几次 ACM 培训、比赛,那你的计算机思维水平要比单纯交几万块钱学费去培训 JAVA 之类的人要高的多。

    至于什么层次。。。初级。。。如果你能用你学到的算法解决 ACM 问题,那层次就高一级了。多刷刷 POJ , ZOJ 之类的吧
    jedihy
        65
    jedihy  
       2016-12-20 15:56:02 +08:00
    @liuchang0812
    @Changxu

    这个真的跟大几,博几没有关系。 kmp 不背就是基本写不出来 bug free 的, stanford 博士也基本写不出。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5216 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 09:26 · PVG 17:26 · LAX 02:26 · JFK 05:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.