复杂度越低的算法就越好么？

[@user_123_0.0]

相似的議題，java中string串接在10^9的量級以下，其時間開銷遠低於實例化stringBuilder的過程，撇除掉string pool的問題，多數情況下直接相加是更快更好閱讀的

[@胡毅-d9g]

很多IDE都會直接幫你優化字串拼接，但是強迫症還是很多

[@Tofusky]

要考慮上這段程式碼在系統中佔用的時間有多少 如果只有10%的時間是花在這段程式碼，你優化到極限程式也頂多快個10%

[@DavidCheng-p1n]

是的，关键是找到瓶颈优化瓶颈

[@RainCat1998]

我喜欢看老哥视频一个重要的原因是，很容易把"码农高天"看成“码农高手”。确实在很多问题是博主讲得也很深入浅出，赞一个！

[@zianmao8583]

因为是真高手😂

[@kingshark8848]

我偶然一次做面试官的时候遇到一个小伙伴，面对我们的编程题，一看到形式立马觉得是个图的路径搜索问题，然后就不可自拔的陷进去了，提示n次也没有摆脱。感觉算法题做多了真会产生一种应激反应

[@balemula]

我觉得，解决一个问题算法有很多种，不能像是文科硬生生往模板上靠，有自己的理解很重要，很多复杂算法的题都有数学上的简单解法

[@taylorlin3214]

很類似被過度預訓練的AI會出現的問題。

[@酷木木]

真实基本上不可能遇到这种情况，通常工作时需求并不是要有多快，而是能执行就行，不然市面上就不会有那么多优化差的程序了，况且老板让你加班你愿意吗？ 事实是真正追求速度的人是因为他本人对速度有个洁僻或是坚持，但这样的人怎么可能会陷入复杂度陷阱呢

[@槑]

没错，大部分时候能跑就行，真遇到瓶颈才值得去专门优化

[@pacersgo]

要看具体情况，我遇到过有人写程序跑1分钟，最后优化到3秒钟的

[@xorpop]

還是要看情況，總得來說，驗證程序邏輯和實現算法是二回事，不過現代電腦真的太快了，一般應用不太需要拼極限

[@svz9g374vp9]

取决于你在什么位置 越接近硬件越需要优化 大部分人都写业务逻辑罢了

[@allenpo]

講的很不錯，沒有100%的絕對，看的是好閱讀和易修改，如果需要大量運算且重複性極高，就要考慮是否為核心運算再去優化，而不是一開始就追求最好的，不外乎就是為了省去後續修改的麻煩嗎🤣。反推心理層面的想法與實際需求都會隨著時間而作調整，最重要的是要保持彈性

[@slan1220]

在工作上，能讓別人看得懂比算法重要太多 我實現的是功能或是商業邏輯，不是來寫算法的，在可接受的性能下最簡單的寫法才是最優

[@netbison9715]

Constant overhead vs O() with practical sample size and focus on the whole script, 这才叫大师, 讲得好!

[@yanaya713]

还以为阿笨直接循环跑十次，每次找最大数就完了，总共10000次。

[@remi4994]

主要Log 在数很小的时候和constant没区别，logn和logk只要n不是上亿级别， logn就是constant

[@王大為]

10:04 時間複雜度最低的方法是用median of medians一個一個挑出來

[@alishchuang9987]

問題明顯是Python 速度的問題 哈哈 但確實很多低複雜度的解法在小樣本裡並不優於簡單高複雜度的算法

[@蔡秉諺-f5g]

跟我的感想一樣。按照定義，複雜度陷阱應該是類似要用 if else 還是 switch case 的問題，可是這個影片所說的問題基本上是因為python沒有對應的底層函式才有的。

[@zeicold]

这是算法问题和语言无关...

[@jianli4787]

@@zeicold 你試試用python寫一個sorted函數（用的是quick sort）再對比速度試試？ built-in的sorted不是用python 寫的，所以速度更快。

[@Yunfinibol]

确实这个例子不算好，但是还有很多算法是虽然复杂度低，但是乘上的常数大到在绝大多数情况下更慢的 而且视频里这个意思也不能说是完全不对，因为没有考虑python自带的“常数复杂度”所以陷入了复杂度陷阱

[@Anzs1152]

程式沒跟隨數學設計 為了降低入門難度使用組合語言才是大問題

[@CalvinJKu]

“Premature optimization is the root of all evil.” - Donald Knuth

[@jianli4787]

因爲你用的是python啊。 如果用C++或者java，可能結果就不一樣了。 python built-in 函數可能是用更底層的語言實現的，所以會比手寫的函數快。 真正的比較是，你手寫一個heap sort和手寫一個quick sort （sorted應該是quick sort吧）處理這個問題看哪個的運行速度更快，我覺得會是heap。

[@Yunfinibol]

但是这个视频的关键就在于因为heap方法用到的python方法多，所以算法的常数大（渐进复杂度其实和用C写是一样的，因为其中用到的python方法不会产生大于n的额外复杂度），如果只考虑复杂度的话就忽略了python本身慢的问题，陷入复杂度陷阱 如果能像你一样意识到常数大的问题，当然就没事了

[@billgameful]

這視頻不是要讓你鑽牛角尖 是要告訴你，完成一個更好的算法，可能會花費更多其他成本 1.開發成本 2.算法初始化成本 但是花了這些成本 你可能會遇到 1.實際情況數量級就是無法抵銷初始化成本 2.開發成本太高 3.整體效能占比不高，重複利用率不高。

[@jianli4787]

@@billgameful 你這都扯到別的地方去了。 LC的「最優算法」在測試數據就已經可以體現出優勢，和你說的各種因素都無關。 但是python經常會做出一些看似優化其實劣化的事情，這需要對這個語言和系統有更深入的了解，這才是本次視頻所產生的問題的根源。

[@dennisliu5641]

那你去寫cython吧，重造輪子時間！ 即便你寫出來了，對人類世界貢獻也不大。 有那個時間去抄別人的最佳演算法，不如多開發兩道產品。

[@jianli4787]

@@dennisliu5641 那我還不如去寫C。

[@millsonliu]

如果從晶片的特性去看，其實就是連加連減在所有算法上．化繁為簡大道若拙．相同道理． 另外數據量確實是一個非常需要考慮的［變量］之一．

[@duzhuo]

省流：别越学越魔怔

[@syutengu]

当然时空复杂度越低越好，这是绝对的，因为讨论的对象“算法”本来就应该在纯理论范畴内被讨论。书写复杂度在实际中非常重要，但是只要它无法被客观准确评价，就无法上升到理论高度。比如行数这个指标，主观暧昧至极。又，把集大成的内建方法和自己实现的某种特定算法比性能、比行数，近乎耍流氓。

[@syutengu]

如果是在讨论如何运用学过的算法，那么确如所言，没事儿最好别乱用。多数比不过集大成的内建方法。尽管取最值用排序好比杀鸡用牛刀（超标完成任务），但如果手边就有一把牛刀，何必现磨一把鸡刀。

[@user-ericshen19555]

歪樓了但這題能O(n)（（

[@cccpwx123]

O(N*log(10))

[@untitledc]

1:30 作者已經說了是 O(n) 沒錯（如果 k 為常數的話）

[@user-ericshen19555]

@@untitledc 不是 這是select problem 不管k是多少都O(n)

[@莱蛙超进化核蛙]

@@user-ericshen19555 所以为什么慢呢？

[@bravexample]

確實，連 sort 都不需要

[@miloyang2358]

很棒的话题 从来没有想到过

[@YuuHuang-b2m]

感觉不能算一个很好的例子，这更像是因为python 本身比C 有更多的多overhead 导致的，我感觉矩阵乘法strassen algo 和正常乘法应该是一个更好的 asymtoptic order 有优势但是performance不好的例子

[@Quick-Bull01]

太好了，我以後都用for，確實是沒差

[@zzzyyyyhhhhh]

但 tim 排序不是 O(n) 到 O(nlog n) 吗，有时候确实比 O(nlog k)快啊

[@b95109028]

能分享到這個地步，我是真佩服高兄了

[@woshiwopa]

把这个问题扩展开来，其实要记住没有正确的/最好的方法，只有合适的方法。有些人就整天把best practice挂在嘴边，全然不顾项目的实际情况

[@lhypds]

绝大多数问题我都直接问ChatGPT，很少有解决不了的，如果解决不了，我就把整个丢进去

[@雪岸翔太]

簡單來說 就是有時候用數得比算的快

[@Ruhgtfo]

😂 別要求高級 直譯語言 太高，除非真的需要才用 tensor-gpu 這個處理 6gb 的CSV 文檔 清除掉 多餘信息 都要跑多少天了。想做 transformer 的基本翻譯model的。這種速度preprocessing+ postprocessing data 都要幾天😅 試過了。特慢

[@brianhsu_hsu]

找分數那題我的第一個直覺也是用內建的函式排序 1000 個分數，然後取前十。反正 1000 的 nlogn 在現在的電腦運算量幾乎等於沒有。XD 這作法程式既簡單好懂又好維護，基本上就是兩個 function call。XD

[@xorpop]

這才是對的，複雜度是數學完美呈現的結果，現實中不是只有數學，還有金錢、時間的問題，都試試看才是正解

[@kyosukearashi3523]

要考慮到維護時人眼人腦辨識系統的速度才是最花時間和資源的

[@lischentejuleour5657]

Premature optimisation is the root of all evil.

[@frankchiou4229]

沒辦法，真正面試不行吧，我一想到暴力解就擔心TLE了，就像這題一想到排序就需要nlogn，就覺得肯定爆，一定還有更好的解法

[@Xilillusion]

复杂度都过于注重O(·)了，这表示的只是最坏的情况

[@yuanbonan5441]

heap要占内存，quick_sort不占内存。。。。

[@terminal2004]

你这是拿Python自己for循环写的低复杂度算法，跟人家直接调用sorted C代码的搞复杂度算法来比。C可是比py快两个数量级的。 这算法用c++写一遍再来比较你就知道了。

[@yanaya713]

请问用heap为啥是nlogK？我觉得就是O(n+K)啊。把所有数据扔到heap里，再弹出10个数就完了。当然heap内部实现是个二叉树还是啥，每次加个数成本都不低吧。

[@porker2008]

你这种做法是O(n + K log n)，建heap是O(n)，弹一个数是O(log n)

[@Eric-u3v3r]

很有道理。让我想到有的数学教授认为 P vs NP 问题毫无意义，因为这两个概念纯属人为构造。比如，也许 P=NP，但是对于NP hard 问题即使存在 P 算法， 这个 P 算法也很可能包含次数很高的项，这样的 P 算法对实际解决问题毫无帮助

[@shoujungu1043]

纯数学是理科，算法是工科。学理科更感兴趣的是探索，而不是优化。

[@蔡秉諺-f5g]

這個問題比你想像的重要，最主要就是在加密破解上的問題，如果加密需要很長時間才能破解，那麼該加密法就是安全的，問題是你要如何證明該加密法不存在快速破解的方法？

[@fromfareast3070]

这个应该不是数学背景的教授，应该是工程学背景教授。因为数学是没有“毫无意义”这种东西的。只有工程学思维才会有“实际解决问题”的想法。

[@fromfareast3070]

@@shoujungu1043 优化的学科叫运筹学，其实也是非常偏理科的。虽然我遇到的教授在工程系教书，但是有非常浓厚的理科思维。

[@s950343]

這題是selection problem 時間複雜度可以到O(n)

[@yung-mingchiu2364]

不只一鍵三連，一鍵六連也沒問題。

[@GaoyuanCao]

但是竞赛真的动不动就1e5*1e5

[@林天逸]

還是有差，我用網頁做了table重新排序，shell sort 硬是比 bubble 快不少

[@wd357dui]

左边4个扩展更新有点强迫症犯了

[@user-djelwJsskI8964]

对 有时候还有vscode更新😂

[@MADorMad]

不就排序後取十就完事？ 低於1秒的差距跟沒有一樣 而且這東西要用什麼算法完全要看幾件事 處理量級 最大允許回應時間

[@kawaifong2844]

如果需要實時響應的情況下，即使少於1秒也會給人明顯的頓挫感

[@MADorMad]

@@kawaifong2844 最下面兩行

[@generalyoutubewatching5286]

有道理

[@yuanbonan5441]

其实现代能用cpu算的东西，基本上都在io了，要是cpu算不过来，强撸GPU就行了

[@海豹-j9v]

然後LEETCODE都給超巨大數字 現實都碰不到

[@minghaoliang4311]

know your code know your algorithm know your library

[@xorpop]

Lib first

[@kunalchang980]

什麼heap 我不服 刷入魔是要 quick select

[@climbingg]

我剛才也一直在想這個😆

[@TheBabelCorner]

有趣

[@Ryan-gf1sz]

好

[@vector4067]

一个partition就好了，快排递归调用的算法。

[@catsd2936]

这里高手多，我在这里问一个题外话：怎么把一个末尾为0的小数转为包括末尾0的字符串？例如3.10，转为'3.10'。

[@TeddyJi]

可以用round函数指定小数的位数，再用str函数转换。

[@catsd2936]

@@TeddyJi 如果我事先并不知道这个小数的位数呢？

[@bruceb1331]

@@catsd2936 大學生菜鳥路過，可能白癡別介意阿 手動補缺額的0是否可行?，例如目標長度4，那就手動補上三個0，'3.1000' 除此以外py可以格式化字串文本輸出

[@TeddyJi]

@@catsd2936 啊？那你怎么知道小数的末尾为零？毕竟末尾为零的小数是不会显示末尾的零的。

[@shungtaidou]

format(3.1, ".2f")或是f"{3.1:.2f}" 這樣是你要的嗎？

[@Gange_Wang]

這根本我 刷leetcode沒有看到您贏過95%python用戶或更高便覺得面目可憎

[@cool_breezegan1880]

明白了

[@MengFanchao]

you effectively messed up and perplexed a few separate yet related concepts, such as asymptotic bounds, empirical running time, Kolmogorov complexity, and even the fundamental computational model used in analyzing complexity. and apparently you forgot the concern in space if you really had to pull this thread this way. in cs pedagory, these concepts and their interrelations are always spelled out again and again, and the instructors would never get tired of doing so. there is no such a concept called "complexity dilemma", but misuse and misunderstanding of complexity analysis.

[@alexz2858]

就当听书看了。

[@잘못-l7m]

我不管，鸵鸟算法才是最吊的

[@expowang6847]

私以为这个例子只能说明时间复杂度对业务不重要，不能说明对算法本事不重要，而且用纯Python来写k largest本身就是一个很糟糕的实现，说服力有限

[@kor-pl3by]

这是个笑话吗？用着python讲算法效率。那是类c和汇编级才需要考虑的。再就是都是log级的，有多大区别。比较的方法也有问题，一个是从头设计算法的套路，一个是调用现成库，本就没有可比性。算法优劣的核心，不是自身的复杂度，而是与硬件的配合--能最大发挥硬件性能的是最好的。如果都差不多，肯定选逻辑明了和常用的。

[@anonymologist7946]

事實上很多公司用 python 或是非compile語言，但考的算法就是這些，可笑吧

[@kor-pl3by]

@@anonymologist7946 说明都是外行指导内行--官僚化的恶果。

[@莱蛙超进化核蛙]

@@anonymologist7946 学魔怔了是这样的。又不是发明语言。应用层卷你妈呢！哎~

[@佑-m6h]

你是清醒的😂

[@MikeSmith-ch5ld]

脚本语言😅

[@bjornandresen9625]

perf first

[@user-abiko_cccc]

脱离使用场景谈算法，就是搞笑来的。真以为这是上大学做脱离实际的算术题啊？笑死！代码都是要拿来实用的，是好是坏拉到生产环境去溜溜不就知道了，到处都是一堆“理论家”，就会夸夸其谈，真的最后程序打包了，上线了，部署了，就知道这些都是些“理论优秀”，到实际生产环境P都不值。😂！

[@TiWang-j5s]

没差现在有ai可以问 请教他我该用哪一种级别的算法就好