原书紧接着还有一句更强的假设,讲义前面漏了,这里补上:RAM 模型假设每条指令花的时间和其他任何一条指令一样,每次数据访问(读一个变量的值或写进一个变量)花的时间也和其他任何一次数据访问一样——换句话说,每条指令、每次数据访问都花常数时间,连按下标取数组元素也是。§3.2 讲的「每行代价 ckc_k 可以互不相同」是伪代码一行的层面(一行由固定几条指令组成),和这句指令层面的一视同仁并不冲突。(CLRS 书页 26)
這段話看不太懂，在大白話的詳細說明次。
15 Matching Annotations
- Last 7 days
-
127.0.0.1:18765 127.0.0.1:18765
-
-
如果允许字无限宽,就能作弊:把整个数组一百万个数全塞进一个超宽的字里,再用一条指令对这个字做操作,等于一步处理了全部数据,任何算法都能「一步完成」
這邊不太理解，我可以理解一個字的大小至少要可以寫得下 c 乘上 log n也就是說至少這個字可以表示出它的 index我這樣理解沒錯吧，可是這一段話我不理解的地方就是說我知道要設定一個上限，不能允許超能力，但是就算把一百萬個數塞進一個超寬的字裡面 那要如何用一條指令，直接對這個字操作，然後這樣子會等於一部數據，所以我不理解的是就算我把很多個數塞進一個超寬的字裡面那我的想像中也是需要經過很多個 instruction 才可以處理全部的數據為什麼這邊可以說一條指令，就可以對一個字操作，然後處理全部數據 ?
-
CLRS 规定:处理规模为 nn 的输入时,一个字是 clog2nc\log_{2} n 位,其中 c≥1c\ge 1 是一个固定常数。这条规定的两半各管一件事,下面分开讲
可是這邊我就看不太懂，因為我收到的資訊是矛盾的，比如說你前面說常見的64位機器，一個字是64，64個 bit，但是你下面又說 CLRS 規定，一個字是這樣子，那到底是，到底是怎麼樣子
-
- Aug 2026
-
127.0.0.1:18765 127.0.0.1:18765
-
面对难比的函数,为什么会先取对数?
還是一樣的問題, 第一次出現的概念 應該是要定義清楚 而不是用反問法問者 這樣寫 是假定讀者已經知道要先取對數 所以你才會問讀者為什麼 可是實際上 讀者是第一次看到這個概念 所以你這種表述方式會讓人莫名奇妙 我已經提過一次 但是你還是再犯 所以肯定有深層的原因導致這個現象 你需要挖掘出來 然後把規則或制度完善好 禁止再次發生 這是給cli agent看得 你不用回答
-
例题七:调和数 H(n) = 1 + 1/2 + 1/3 + … + 1/n = Θ(lg n)(102 台大資工)。
這類題目要把示意圖等等的話出來 如果原教材的解答有畫圖 你不能省 如果沒有話題 你依照題目判斷常規解法都要有圖 那你也要畫出來
這是給cli agent看的 不須回答
-
Stirling 近似(§3.11)
同樣的問題再犯, 1.講了一個前面沒定義過的東西, 2.這個東西為何露講 你無須回答 我會讓cli agent檢討
-
lg(n!) ≥ lg n + lg(n−1) + … + lg⌈n/2⌉ ≥ ⌈n/2⌉·lg⌈n/2⌉ ≥ (n/2)·lg(n/2) = (n/2)(lg n − 1)
這邊高斯符號要取天花板還是地板 沒有講清楚 為何
-
解:f₁(n) = n²,f₂(n) = 2n²。
例題的解也用縮放方式可以隱藏起來
-
札記 1-8:取对数后,哪些比较可以安全搬回原函数 在对数有定义、而且 g(n) 随 n 增长到无穷的前提下,林立宇札記 1-8 给出三条比较原则。前两条可用,第三条不可以:
這邊講法很怪, 我一再強調任何東西第一次提出來要先給出完整詳細的概念, 你第一句話說"哪些可以..."隱含的意思就是假設讀者已經知道這個概念 讓人看得莫名其妙
-
原书的证明借道对数:lg(nb) = b·lg n = Θ(lg n),而 lg(an) = n·lg a = Θ(n)。因为 lg n = o(n),取对数后一个是 o 另一个,再由 §3.11 的札記 1-8 第 (1) 条(取对数后严格更小 ⟹ 原函数严格更小)得 nb = o(an)。
批評 1. 要這樣證明 你首先要確保前面有提過這個lemma或概念, 如果是很久以前提過的 你可以再把完整概念or公式寫出來一次 2. 為何會漏掉這個札記提到的概念? 教材應該要完整禁止自行刪減任何東西才對
這邊沒有要你回答任何問題 我會透過cli 那邊讓agent看到
-
又因为 f + g ≥ h(两个非负数之和不小于其中较大者
這邊看不懂
-
CLRS 给的解读规则是:「不管左边的匿名函数怎么选,右边总有一种选法让等式成立」——右边永远比左边粗糙。链式写法 2n² + 3n + 1 = 2n² + Θ(n) = Θ(n²) 就是靠这条规则一路变粗的
這邊沒看懂 講清楚
-
-
127.0.0.1:18765 127.0.0.1:18765
-
把一个数的二进制位整体左移 1 位等于乘 2
why?
-
为什么字长又不能随便大?(上限) 如果允许字无限宽,就能作弊:把整个数组一百万个数全塞进一个超宽的字里,然后用一条指令对这个字做操作——等于一步处理了全部数据,任何算法都能"一步完成"。这和"一步排序"的超能力指令是同一种作弊。
can you give me an example, using this method you mentioned as a super power?
-
什么是"字"(word)?
我以前讀到8bits= 1byte, 4bytes = 1word 這是準確的嗎? 適用於這邊的word嗎?
-