【漫士科普】分而治之:算法背后的哲学智慧

แชร์
ฝัง
  • เผยแพร่เมื่อ 11 ธ.ค. 2024

ความคิดเห็น • 53

  • @kait6540
    @kait6540 4 หลายเดือนก่อน +21

    可能英文的內容看比較多,divide and conquer 的中文「分治」倒是第一次看到,不過這是一個不錯的翻譯,「分而治之」簡單清楚的表達了演算法的精髓。

  • @qazwsxedcrf
    @qazwsxedcrf 4 หลายเดือนก่อน +15

    拼L型地磚的問題我有一個想法,首先我們要明白一種拼法
    ⬛⬛🔳🔳
    ⬛⬜⬜🔳
    🔲⬜
    🔲🔲

    • @manshi_math
      @manshi_math  4 หลายเดือนก่อน +1

      這也是一種正確的遞歸思路!

  • @超級無情大熊貓
    @超級無情大熊貓 4 หลายเดือนก่อน +2

    我的教授曾經跟我說過有的電腦科學家甚至把log(n)當作是常數時間,為什麼?因為就算是n=10^18這種天文數字,在log(n)的洗禮之下也僅僅只需要100000次計算便結束了,是非常威猛的一個加速,矩陣快速冪尤其精彩😂。

  • @ginnnho
    @ginnnho 4 หลายเดือนก่อน +1

    其實看這種影片真的讓我提升更多對問題的想法

  • @yujeong8373
    @yujeong8373 4 หลายเดือนก่อน +1

    個人的看法是動態規劃比分而治之更精彩

  • @石懷仁
    @石懷仁 4 หลายเดือนก่อน +2

    影片1:48處,50張卷子共須經過幾次查找:您影片上寫的是50+49+48....+1=1250,但其實從50+49+48....+1應=1275才對

    • @kiscyn
      @kiscyn 2 หลายเดือนก่อน

      不应该加哪个50,答案应该是1225

  • @特別的特特special_TT
    @特別的特特special_TT 4 หลายเดือนก่อน +2

    我平常作這種事情用的方法是:
    1.記錄第一項目值
    2.如果第二項目值

    • @cookie12307
      @cookie12307 4 หลายเดือนก่อน +1

      聽你說的應該是泡沫排序,這排序方式效率不高。但如果要排的東西不多的話也能湊合著用

    • @mmmaaarrrkkk
      @mmmaaarrrkkk 4 หลายเดือนก่อน

      @@cookie12307 應該是插入排序,不過確實也偏慢

    • @cookie12307
      @cookie12307 4 หลายเดือนก่อน

      @@mmmaaarrrkkk 他交換完繼續往後掃,這是泡沫排序吧

  • @yankj7647
    @yankj7647 4 หลายเดือนก่อน +3

    這熟悉的口音好像從哪聽過

  • @cookie12307
    @cookie12307 4 หลายเดือนก่อน

    感覺merge sort會比較好理解,而且也是用分治的想法

  • @spacefreedom
    @spacefreedom 4 หลายเดือนก่อน +7

    这排序总让我想到图灵机的那个问题,“自我调用”,包括前边康托尔的那个集合的势的证明。这种“自我调用”、“自我指涉”,总觉得理解不够透彻本质,博主能不能讲一讲,如何理解这里边的矛盾和悖论,如何让这种逻辑自洽,数学第三次危机到底怎么样了。

  • @Peter-r4h9q
    @Peter-r4h9q 4 หลายเดือนก่อน

    方塊問題我倒是想到
    如果擺著看
    就是3個邊邊一塊和一個不一樣
    這樣就可以化解成
    解2組方塊,因為邊邊一個的用複製貼上就好
    只有單獨被拿走的要演算

  • @duoiaa
    @duoiaa 4 หลายเดือนก่อน +3

    经常当课代表的同学...

  • @恩恩-c8e
    @恩恩-c8e 4 หลายเดือนก่อน +2

    中位數在一開始是不可能知道的吧,知道不就是排好的時候嗎?
    所以區分的標準數字到底怎麼取,隨機嗎?
    這樣和理想中以中位數來執行的效率會差很多嗎?

    • @haoyuli9
      @haoyuli9 4 หลายเดือนก่อน +5

      @@恩恩-c8e 问题问的很不错哦,标准数字是随机取的,一般在编程中取一个数组位置中某一个,比如最右边。这样的确会导致最坏情况,即选择的数永远都是最大那个会最小那个。但是几率很小,所以看平均情况下表现。

    • @mmmaaarrrkkk
      @mmmaaarrrkkk 4 หลายเดือนก่อน +1

      如果很擔心遇到最壞情況,可以隨機取三個,選中間的一個作為基準數,可以改善運氣問題

  • @蔡秉諺-f5g
    @蔡秉諺-f5g 4 หลายเดือนก่อน +6

    話說之前搞程式的時候,無意間發現快速排序有一個BUG,這個BUG導致手游上的排行榜結算速度非常的慢。
    這個BUG像是房間裡的大象,但是我看到了就是不說,欸,就是玩。
    (這麼有趣的BUG,當然要當自己的題材)

    • @micako6309
      @micako6309 4 หลายเดือนก่อน +1

      那你倒是發影片阿😂(敲碗

    • @rex-coding
      @rex-coding 4 หลายเดือนก่อน

      基本上就是發生在降序或升序排列 (已經排好了),才會有這樣的問題
      如果作為分割序列的值,是抓最前面或最後面的話

    • @yichenyin7138
      @yichenyin7138 4 หลายเดือนก่อน

      虽然说快排在逆序时确实会退化成n2复杂度,但目前的工程实现早就通过事先随机打乱而克服了吧😂

    • @蔡秉諺-f5g
      @蔡秉諺-f5g 4 หลายเดือนก่อน

      @@yichenyin7138 隨機打亂確實可以加速,但你確定要先隨機打亂嗎?幹嘛不直接使用氣泡排序?
      另外,一般手游都是用開源的DB,這些DB不會預設資料是亂序的?

    • @doge7562
      @doge7562 3 หลายเดือนก่อน

      @@yichenyin7138 只能減少遇到的機率但是不能避免完全不會遇到
      但是平均而言快速排序已經是非穩定排序中很優秀的排序法了

  • @Vincent778520
    @Vincent778520 4 หลายเดือนก่อน +3

    4:06 33跟27順序反囉

  • @3152蔡孟憬
    @3152蔡孟憬 4 หลายเดือนก่อน +2

    漫士大大好,我想請教一個可能很笨的問題:
    在拼地磚的例子中把一塊L形磚放到中間,將方格切成四個象限。我想問的是雖然四個區域各缺了一塊,但缺的位置不一樣,為什麼可以直接說他們是相同的子問題呢?

    • @gamerpotato6667
      @gamerpotato6667 4 หลายเดือนก่อน +1

      因為題目是在8x8格子裡隨機摳掉一塊,而4x4的角落摳掉一塊,後者是前者的其中一種模式,稱作"子問題",同時兩種問題可以用"相同"的方法解決。
      此處應是著重在概念相同
      打個比方好了,一開始的分數排序問題,稍作變化,若低於70分老師會用紅筆批改,70分以上用橘色的筆。雖然你不並知道分界點是70,你知道橘色的分數一定比紅色的分數高。
      你仍然可以無視顏色,隨機選33用快速排序來完成任務,那麼就像磚塊問題,由於顯而易見的,橘色一定比紅色大,那分割出來的子問題顏色分布也會不相同,但仍可以忽略這點,用"相同"的思路去解題。

  • @crayonlimulus
    @crayonlimulus วันที่ผ่านมา

    突然想到FFT

  • @石懷仁
    @石懷仁 4 หลายเดือนก่อน +1

    請教:影片1:40處,10張卷子共須經過50幾次的查找:您的影片上寫的數字是57,但從10+9+8....+1=55,請問為何不是55次?

    • @kiscyn
      @kiscyn 2 หลายเดือนก่อน

      其实比较只有,5x9=45,57我也不知道哪里来的。按道理应该有俩数字,一个是比较次数,一个是访问次数

  • @haoyuli9
    @haoyuli9 4 หลายเดือนก่อน +1

    我觉得对我来说难点还有一个,如何把这个思维过程变成代码实现

    • @rex-coding
      @rex-coding 4 หลายเดือนก่อน

      排序的問題可找 “快速排序法 (quick sort)”

    • @lizard6881
      @lizard6881 2 หลายเดือนก่อน

      qsort(ptr*)

  • @HiHi-jy1dj
    @HiHi-jy1dj 4 หลายเดือนก่อน

    我好奇如果用三分之會不會更快

  • @billgameful
    @billgameful 4 หลายเดือนก่อน

    看到排序有時就會無聊想著,現在電腦的記憶體容量也不小了,能不能直接用空間換時間來排序。

  • @石懷仁
    @石懷仁 4 หลายเดือนก่อน

    影片4:30處,您影片上左下角的(共須經過幾次查找)數字為2:請問為何不是4(而是2)?

  • @金毛強23
    @金毛強23 4 หลายเดือนก่อน +1

    说起分而治之就让我想起Jango Y,你们是同行吗。

  • @user-ts5xg5ez8k
    @user-ts5xg5ez8k 4 หลายเดือนก่อน +2

    拿视频中的10张卷子举例
    假设随机拿张卷子假设是23再重头开始拿卷子整理小于放前面大于放后面
    我们就可以拿到
    23 67
    19 23 67
    8 19 23 67
    8 19 23 67 98
    8 19 23 33 67 98
    8 11 19 23 33 67 98
    8 11 19 23 27 33 67 98
    8 11 19 23 27 23 55 67 98
    8 11 19 23 27 23 45 55 67 98
    请问这方法和视频里是同样的概念吗?

    • @user-ts5xg5ez8k
      @user-ts5xg5ez8k 4 หลายเดือนก่อน

      就我不是从小-大这样排,是以当前的情况来排列这样似乎也能提高许多效率

    • @蔡秉諺-f5g
      @蔡秉諺-f5g 4 หลายเดือนก่อน +6

      不同,這是另一個排序法,叫插入排序

    • @cookie12307
      @cookie12307 4 หลายเดือนก่อน

      ​@@蔡秉諺-f5g這連排序都不是吧

    • @蔡秉諺-f5g
      @蔡秉諺-f5g 4 หลายเดือนก่อน +1

      @@cookie12307 不,這也是排序法,只要吧亂序排成有序的方法,都是排序法

    • @cookie12307
      @cookie12307 4 หลายเดือนก่อน

      @@蔡秉諺-f5g 我其實看不太懂他上面在說什麼,但他到那串數列也不是排序好的,所以我才這麼說。而且我感覺不出他說的方法跟插入排序的關係

  • @saaing864
    @saaing864 4 หลายเดือนก่อน

    哈佛大学威尔逊主张融合科学与人文探索中优秀和实用的精华,发展全新的哲学。墨子在人类历史上最早提出的世界主义、效益主义、和平主义、非命主义是人文探索的有益和实用的精华。今人可以站在墨子的肩上发展墨学,依据最新的科学研究论证墨子思想中合理的部分,批判错误的部分,补充缺失的部分,发展有益的部分,改造出新墨学。新墨学依据科学扩展兼爱,不但兼爱人,而且兼爱动物,兼爱生态,兼爱养育人类的地球。拓展的兼爱是更高层次的道德思维,是为天下人和动物的生存和美好生活呐喊,增加幸福总量,提高人类和动物的生存能力。威尔逊认为最应该做的是推动生态保护,而不是在探索星际旅行方面浪费资源。医学研究发现爱他人和爱动物都可以增进自己的健康,利他也利己。谋求利他和利己让人得到意义,得到快乐,得到健康,得到长寿,增加幸福总量

  • @codecatrunning
    @codecatrunning 4 หลายเดือนก่อน +1

    简单总结下 就是外包 自己搞不定的就外包出去 接包方有搞不定的就再包出去一部分 层层外包 怪不得印度人软件人才多 都是懂算法哲学的