【漫士科普】分而治之：算法背后的哲学智慧
HTML-код
- Опубликовано: 27 ноя 2024
- 一位来自清华的人工智能博士生，日常思索和科普。
An artificial intelligence doctoral student from Tsinghua University who likes to delve into thinking and science popularization.
喜欢我的内容欢迎订阅、评论、点赞^_^
Welcome to subscribe, like, and leave comments under my videos^_^
打开小铃铛🔔获取频道最新动态
Turn on the little bell🔔 to receive my latest updates
--------------------------------------------------------------------------------------
#科学 #科普 #知识 #物理 #数学
可能英文的內容看比較多，divide and conquer 的中文「分治」倒是第一次看到，不過這是一個不錯的翻譯，「分而治之」簡單清楚的表達了演算法的精髓。
拼L型地磚的問題我有一個想法，首先我們要明白一種拼法
⬛⬛🔳🔳
⬛⬜⬜🔳
🔲⬜
🔲🔲
這也是一種正確的遞歸思路！
我的教授曾經跟我說過有的電腦科學家甚至把log(n)當作是常數時間，為什麼？因為就算是n=10^18這種天文數字，在log(n)的洗禮之下也僅僅只需要100000次計算便結束了，是非常威猛的一個加速，矩陣快速冪尤其精彩😂。
其實看這種影片真的讓我提升更多對問題的想法
個人的看法是動態規劃比分而治之更精彩
我平常作這種事情用的方法是：
1.記錄第一項目值
2.如果第二項目值
聽你說的應該是泡沫排序，這排序方式效率不高。但如果要排的東西不多的話也能湊合著用
@@cookie12307 應該是插入排序，不過確實也偏慢
@@mmmaaarrrkkk 他交換完繼續往後掃，這是泡沫排序吧
影片1:48處，50張卷子共須經過幾次查找：您影片上寫的是50+49+48....+1=1250，但其實從50+49+48....+1應=1275才對
不应该加哪个50，答案应该是1225
方塊問題我倒是想到
如果擺著看
就是3個邊邊一塊和一個不一樣
這樣就可以化解成
解2組方塊，因為邊邊一個的用複製貼上就好
只有單獨被拿走的要演算
感覺merge sort會比較好理解，而且也是用分治的想法
這熟悉的口音好像從哪聽過
中位數在一開始是不可能知道的吧，知道不就是排好的時候嗎？
所以區分的標準數字到底怎麼取，隨機嗎？
這樣和理想中以中位數來執行的效率會差很多嗎？
@@恩恩-c8e 问题问的很不错哦，标准数字是随机取的，一般在编程中取一个数组位置中某一个，比如最右边。这样的确会导致最坏情况，即选择的数永远都是最大那个会最小那个。但是几率很小，所以看平均情况下表现。
如果很擔心遇到最壞情況，可以隨機取三個，選中間的一個作為基準數，可以改善運氣問題
经常当课代表的同学...
这排序总让我想到图灵机的那个问题，“自我调用”，包括前边康托尔的那个集合的势的证明。这种“自我调用”、“自我指涉”，总觉得理解不够透彻本质，博主能不能讲一讲，如何理解这里边的矛盾和悖论，如何让这种逻辑自洽，数学第三次危机到底怎么样了。
漫士大大好，我想請教一個可能很笨的問題：
在拼地磚的例子中把一塊L形磚放到中間，將方格切成四個象限。我想問的是雖然四個區域各缺了一塊，但缺的位置不一樣，為什麼可以直接說他們是相同的子問題呢？
因為題目是在8x8格子裡隨機摳掉一塊，而4x4的角落摳掉一塊，後者是前者的其中一種模式，稱作"子問題"，同時兩種問題可以用"相同"的方法解決。
此處應是著重在概念相同
打個比方好了，一開始的分數排序問題，稍作變化，若低於70分老師會用紅筆批改，70分以上用橘色的筆。雖然你不並知道分界點是70，你知道橘色的分數一定比紅色的分數高。
你仍然可以無視顏色，隨機選33用快速排序來完成任務，那麼就像磚塊問題，由於顯而易見的，橘色一定比紅色大，那分割出來的子問題顏色分布也會不相同，但仍可以忽略這點，用"相同"的思路去解題。
4:06 33跟27順序反囉
影片4:30處，您影片上左下角的(共須經過幾次查找)數字為2：請問為何不是4(而是2)?
請教：影片1:40處，10張卷子共須經過50幾次的查找：您的影片上寫的數字是57，但從10+9+8....+1=55，請問為何不是55次？
其实比较只有，5x9=45,57我也不知道哪里来的。按道理应该有俩数字，一个是比较次数，一个是访问次数
話說之前搞程式的時候，無意間發現快速排序有一個BUG，這個BUG導致手游上的排行榜結算速度非常的慢。
這個BUG像是房間裡的大象，但是我看到了就是不說，欸，就是玩。
(這麼有趣的BUG，當然要當自己的題材)
那你倒是發影片阿😂（敲碗
基本上就是發生在降序或升序排列 (已經排好了)，才會有這樣的問題
如果作為分割序列的值，是抓最前面或最後面的話
虽然说快排在逆序时确实会退化成n2复杂度，但目前的工程实现早就通过事先随机打乱而克服了吧😂
@@yichenyin7138 隨機打亂確實可以加速，但你確定要先隨機打亂嗎？幹嘛不直接使用氣泡排序？
另外，一般手游都是用開源的DB，這些DB不會預設資料是亂序的？
@@yichenyin7138 只能減少遇到的機率但是不能避免完全不會遇到
但是平均而言快速排序已經是非穩定排序中很優秀的排序法了
我好奇如果用三分之會不會更快
我觉得对我来说难点还有一个，如何把这个思维过程变成代码实现
排序的問題可找 “快速排序法 (quick sort)”
qsort(ptr*)
看到排序有時就會無聊想著，現在電腦的記憶體容量也不小了，能不能直接用空間換時間來排序。
拿视频中的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
请问这方法和视频里是同样的概念吗？
就我不是从小－大这样排，是以当前的情况来排列这样似乎也能提高许多效率
不同，這是另一個排序法，叫插入排序
@@蔡秉諺-f5g這連排序都不是吧
@@cookie12307 不，這也是排序法，只要吧亂序排成有序的方法，都是排序法
@@蔡秉諺-f5g 我其實看不太懂他上面在說什麼，但他到那串數列也不是排序好的，所以我才這麼說。而且我感覺不出他說的方法跟插入排序的關係
哈佛大学威尔逊主张融合科学与人文探索中优秀和实用的精华，发展全新的哲学。墨子在人类历史上最早提出的世界主义、效益主义、和平主义、非命主义是人文探索的有益和实用的精华。今人可以站在墨子的肩上发展墨学，依据最新的科学研究论证墨子思想中合理的部分，批判错误的部分，补充缺失的部分，发展有益的部分，改造出新墨学。新墨学依据科学扩展兼爱，不但兼爱人，而且兼爱动物，兼爱生态，兼爱养育人类的地球。拓展的兼爱是更高层次的道德思维，是为天下人和动物的生存和美好生活呐喊，增加幸福总量，提高人类和动物的生存能力。威尔逊认为最应该做的是推动生态保护，而不是在探索星际旅行方面浪费资源。医学研究发现爱他人和爱动物都可以增进自己的健康，利他也利己。谋求利他和利己让人得到意义，得到快乐，得到健康，得到长寿，增加幸福总量
说起分而治之就让我想起Jango Y，你们是同行吗。
简单总结下 就是外包 自己搞不定的就外包出去 接包方有搞不定的就再包出去一部分 层层外包 怪不得印度人软件人才多 都是懂算法哲学的