題目叫“高性能計(jì)算筆記燈泡開關(guān)問(wèn)題的數(shù)學(xué)優(yōu)化與常數(shù)級(jí)解法”先別被“高性能計(jì)算”四個(gè)字唬住。這個(gè)經(jīng)典題本身很簡(jiǎn)單就是在100盞燈、100輪開關(guān)的設(shè)定里第i輪翻轉(zhuǎn)所有編號(hào)為i的倍數(shù)的燈泡問(wèn)最后哪些燈亮著。可它背后那條數(shù)學(xué)鏈路從暴力循環(huán)一路走到常數(shù)級(jí)判定才是真正值得反復(fù)琢磨的東西也是高性能場(chǎng)景里最常遇到的思維模式能用數(shù)學(xué)化簡(jiǎn)的絕不靠循環(huán)硬算。我最初接觸這個(gè)題是在一次算法面試熱身里后來(lái)發(fā)現(xiàn)很多刷題網(wǎng)站、競(jìng)賽入門題都喜歡拿它當(dāng)“簡(jiǎn)單題”處理。但簡(jiǎn)單題不等于沒有價(jià)值。恰恰是這種題目能把約數(shù)理論、奇偶性分析、復(fù)雜度優(yōu)化串起來(lái)講透對(duì)準(zhǔn)備面試的人、寫底層工具的人、甚至做數(shù)值仿真的人都很有用。這篇筆記不打算只給結(jié)論我想把“燈泡開關(guān)問(wèn)題”從最樸素的實(shí)現(xiàn)開始一步步演化到 O(1) 判定和 O(√n) 構(gòu)造答案的完整思路并順帶聊聊延伸變體和實(shí)際工程里會(huì)踩的坑。無(wú)論你是在校學(xué)生、算法愛好者還是寫高性能服務(wù)的工程師這套分析過(guò)程都值得看下去。1. 開場(chǎng)這個(gè)經(jīng)典題到底在考什么先把題目再明確一遍因?yàn)榫W(wǎng)上流傳的版本太多有100盞燈、100個(gè)人的也有n盞燈、n輪的通用版。為了后面推導(dǎo)方便我統(tǒng)一用通用描述有 n 盞燈初始全部熄滅第 i 輪i 從 1 到 n將編號(hào)能被 i 整除的所有燈做一次狀態(tài)翻轉(zhuǎn)亮變滅、滅變亮最終統(tǒng)計(jì)哪些燈處于亮著狀態(tài)。一眼看過(guò)去這就是個(gè)模擬題甚至不需要?jiǎng)幽X。但真正參加過(guò)面試或者自己動(dòng)手寫過(guò)的人會(huì)有感覺模擬能做問(wèn)題是當(dāng) n 變大時(shí)模擬的成本會(huì)迅速失控。假設(shè) n 100內(nèi)層總操作次數(shù)大約是 n × (1/1 1/2 ... 1/n) ≈ n ln n也就是幾百次毫無(wú)壓力?？蓳Q成 n 10^7 或 10^8模擬一次可能要跑幾十秒甚至更久內(nèi)存還要開一個(gè) n 大小的布爾數(shù)組在資源敏感的應(yīng)用里這就是災(zāi)難。所以這個(gè)題真正想考察的不是你會(huì)不會(huì)寫兩層循環(huán)而是你愿不愿意停下來(lái)想想每個(gè)燈泡到底被翻轉(zhuǎn)了多少次這個(gè)“翻轉(zhuǎn)次數(shù)”背后有沒有規(guī)律一旦想通了這個(gè)問(wèn)題就從“需要遍歷所有輪次”變成“只需要判斷一個(gè)數(shù)是否為完全平方數(shù)”直接跨到常數(shù)級(jí)解法計(jì)算量可以被壓縮到幾乎為零。這也是我為這篇筆記標(biāo)題加上“高性能計(jì)算”的原因高性能并不是指把循環(huán)寫得多漂亮而是指找到一種計(jì)算模型讓很多原本要執(zhí)行的操作在數(shù)學(xué)上被抵消掉。接著我會(huì)從最笨的方法開始寫相信我這個(gè)演進(jìn)過(guò)程比最終結(jié)論有意思得多也是理解“常數(shù)級(jí)解法”的一把鑰匙。2. 暴力解法與復(fù)雜度的第一層優(yōu)化2.1 雙層循環(huán)的暴力版本先給最直白的實(shí)現(xiàn)思路開一個(gè)長(zhǎng)度為 n1 的布爾數(shù)組初始全 false表示燈滅然后從 i 1 到 n 遍歷輪次內(nèi)層從 j i 到 n每次步進(jìn) i把燈 j 的狀態(tài)取反。用 JavaScript 寫就是這樣。function lampsBruteForce(n) { const lights new Array(n 1).fill(false); for (let i 1; i n; i) { for (let j i; j n; j i) { lights[j] !lights[j]; } } const result []; for (let k 1; k n; k) { if (lights[k]) result.push(k); } return result; }這段代碼邏輯沒毛病也算好懂。但它的總操作次數(shù)是 n/1 n/2 ... n/n n × H(n)其中 H(n) 是調(diào)和數(shù)約等于 ln n γ。時(shí)間復(fù)雜度是 O(n log n)空間復(fù)雜度 O(n)。當(dāng) n 是 10^5 時(shí)很輕松n 到 10^7 開始喘n 到 10^8 基本就得等好一會(huì)兒了。我實(shí)測(cè)過(guò)一次在本機(jī)跑 n 10^8兩層循環(huán)的版本大概要 6 到 8 秒內(nèi)存還要 100MB 左右的布爾數(shù)組。純粹為了拿答案這太奢侈了。如果放在一個(gè)實(shí)時(shí)性要求高的系統(tǒng)里哪怕只是讓用戶等 0.5 秒這種實(shí)現(xiàn)都會(huì)被直接打回。2.2 單層循環(huán)統(tǒng)計(jì)切換次數(shù)稍微想一下我們其實(shí)并不關(guān)心過(guò)程只關(guān)心每盞燈最終是亮還是滅。而亮滅取決于這盞燈被翻轉(zhuǎn)了多少次翻轉(zhuǎn)奇數(shù)次則亮翻轉(zhuǎn)偶數(shù)次則滅。于是問(wèn)題可以改成“統(tǒng)計(jì)每個(gè)編號(hào)有多少個(gè)約數(shù)”。代碼可以寫成下面這樣雖然時(shí)間復(fù)雜度沒降但省掉了一個(gè)大數(shù)組的反復(fù)寫入常量因子小了很多。function lampsCountDivisor(n) { const result []; for (let k 1; k n; k) { let cnt 0; for (let d 1; d * d k; d) { if (k % d 0) { cnt (d * d k) ? 1 : 2; } } if (cnt % 2 1) result.push(k); } return result; }這個(gè)版本已經(jīng)是“先簡(jiǎn)化模型再優(yōu)化實(shí)現(xiàn)”的思路了不去模擬每一輪翻轉(zhuǎn)而是直接把約數(shù)個(gè)數(shù)算出來(lái)。可如果你真的把代碼跑一遍會(huì)發(fā)現(xiàn)它依然是 O(n√n) 的復(fù)雜度——對(duì)每個(gè) k 都要枚舉到 √k總共 O(n√n)比原始的雙層循環(huán)還慢。問(wèn)題出在哪里出在“枚舉約數(shù)”這個(gè)動(dòng)作本身不便宜。所以真正的優(yōu)化從來(lái)不是換一種同樣規(guī)模的計(jì)算方式而是找到一種方法直接跳過(guò)絕大多數(shù)計(jì)算量。這也正是第三部分要講的數(shù)學(xué)結(jié)構(gòu)約數(shù)配對(duì)與完全平方數(shù)。3. 核心數(shù)學(xué)優(yōu)化約數(shù)配對(duì)與完全平方數(shù)3.1 約數(shù)的成對(duì)出現(xiàn)燈泡狀態(tài)和約數(shù)個(gè)數(shù)之間建立聯(lián)系之后我們只需要回答一個(gè)問(wèn)題什么時(shí)候一個(gè)數(shù)的約數(shù)個(gè)數(shù)是奇數(shù)先從直覺入手。任取一個(gè)正整數(shù) n如果 d 是 n 的約數(shù)那么 n/d 也一定是 n 的約數(shù)。比如 12 的約數(shù)有 1、2、3、4、6、12我把它們兩兩配對(duì)1×122×63×4正好配成 3 對(duì)所以 12 有 6 個(gè)約數(shù)是偶數(shù)。這個(gè)“成對(duì)出現(xiàn)”的性質(zhì)幾乎對(duì)所有數(shù)都成立唯一的例外發(fā)生在 d n/d也就是 d2 n 的時(shí)候這時(shí) d 和自己配對(duì)只算一個(gè)約數(shù)而不是兩個(gè)。生活化一點(diǎn)可以想象大家在排隊(duì)找搭檔組合大多數(shù)人的搭檔都能兩兩配好只有站在正方形中心的那個(gè)人只能和自己組隊(duì)于是總?cè)藬?shù)就是奇數(shù)。這個(gè)“中心點(diǎn)”對(duì)應(yīng)到整數(shù)里就是完全平方數(shù)。3.2 奇偶性與亮燈判定有了上面的結(jié)論整道題的答案就浮出水面了編號(hào)為完全平方數(shù)的燈約數(shù)個(gè)數(shù)是奇數(shù)個(gè)其余編號(hào)的燈約數(shù)個(gè)數(shù)是偶數(shù)個(gè)。因?yàn)榧s數(shù)個(gè)數(shù)等于被翻轉(zhuǎn)次數(shù)而翻轉(zhuǎn)奇數(shù)次意味著燈亮著所以最終亮著的燈恰好就是 1, 4, 9, 16, 25 ... 這些完全平方數(shù)。用 n 100 代入亮著的燈號(hào)是 1, 4, 9, 16, 25, 36, 49, 64, 81, 100正好 10 盞。跑一個(gè)簡(jiǎn)單的驗(yàn)證腳本就能確認(rèn)。import math def last_lights_on(n): ans [] for i in range(1, n 1): d int(math.isqrt(i)) if d * d i: ans.append(i) return ans print(last_lights_on(100)) # [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]這段代碼里我用 isqrt 而不是 sqrt就是為了避免浮點(diǎn)誤差。它能直接驗(yàn)證理論結(jié)論和真實(shí)模擬完全一致而且速度比你寫任何兩層循環(huán)都快。到這里“燈泡開關(guān)問(wèn)題”已經(jīng)從模擬題變成了一道數(shù)學(xué)判斷題。3.3 數(shù)學(xué)分析的高性能意義有讀者可能覺得所以呢不就是鑒了個(gè)完全平方數(shù)嗎千萬(wàn)別小看這一步。它直接把問(wèn)題的性質(zhì)改變了。原來(lái)我們要維護(hù)一個(gè)長(zhǎng)度為 n 的狀態(tài)數(shù)組反復(fù)翻轉(zhuǎn)數(shù)據(jù)現(xiàn)在只需要對(duì)每個(gè)編號(hào)做一次完全平方判斷甚至不需要構(gòu)造數(shù)組。隨著 n 增大內(nèi)存從 O(n) 降到 O(1)計(jì)算量從 O(n log n) 降到 O(n)而且每盞燈的判定是常數(shù)時(shí)間。在實(shí)際工程里“把一個(gè)問(wèn)題降復(fù)雜度”往往比“把同復(fù)雜度代碼優(yōu)化 20%”重要得多。舉個(gè)例子如果你在百萬(wàn)級(jí)數(shù)據(jù)管道里做某個(gè)狀態(tài)篩選用滿內(nèi)存的數(shù)組模擬和用數(shù)學(xué)判定直接篩選前者可能拖垮整個(gè)節(jié)點(diǎn)的資源后者連一個(gè)緩存行都用不滿。這也就是為什么很多高性能計(jì)算領(lǐng)域的老手遇到數(shù)學(xué)相關(guān)問(wèn)題時(shí)第一反應(yīng)是找閉式解而不是拼命調(diào)循環(huán)。4. 常數(shù)級(jí)解法直接構(gòu)造答案4.1 從“判斷每盞燈”到“枚舉平方數(shù)”既然最終亮著的燈都是完全平方數(shù)那與其遍歷 1 到 n再逐個(gè)判斷是否平方數(shù)不如直接從 1 開始枚舉 i輸出 i2直到 i2 n。復(fù)雜度從 O(n) 進(jìn)一步降為 O(√n)這個(gè)差距在 n 很大時(shí)非?？植?。比如 n 10^12O(n) 可能要幾分鐘O(√n) 只要幾毫秒。單盞燈的判定仍然可以做到 O(1) 常數(shù)級(jí)這也是標(biāo)題里“常數(shù)級(jí)解法”的由來(lái)給任意一個(gè)編號(hào) k判斷這盞燈最終是否亮著就是判斷 k 是否為完全平方數(shù)一步數(shù)學(xué)運(yùn)算搞定不依賴 n 的大小。代碼也非常短。function solution(n) { const ans []; for (let i 1; i * i n; i) { ans.push(i * i); } return ans; }這個(gè)版本沒有任何數(shù)組狀態(tài)的維護(hù)沒有輪次循環(huán)只有一次冪方比較。兩個(gè)核心點(diǎn)i * i 可能溢出需要用安全的乘法或 BigInt見常見問(wèn)題部分枚舉邊界是 i * i n也就是 i √n不是 i n。4.2 為什么叫“常數(shù)級(jí)解法”我先把術(shù)語(yǔ)邊界說(shuō)明白免得讀者被“常數(shù)級(jí)”誤導(dǎo)。嚴(yán)格來(lái)說(shuō)如果問(wèn)題是“給定 n列出所有亮著的燈的編號(hào)”那答案有約 √n 個(gè)必然至少需要 O(√n) 的輸出量不可能做到 O(1)。但如果是“給定 n 和 k問(wèn)第 k 盞燈最后亮不亮”那這道題的解法確實(shí)是 O(1)判斷 k 是否為完全平方數(shù)。所以最好的描述是算法對(duì)“單點(diǎn)查詢”是常數(shù)級(jí)對(duì)“枚舉全部答案”是 O(√n)。這個(gè)區(qū)別在做技術(shù)方案評(píng)審時(shí)一定要講清楚不然容易被追問(wèn)“你 O(1) 怎么還要循環(huán)輸出答案”。提示面試和文檔里最好明確寫“常數(shù)時(shí)間查詢O(1)枚舉答案O(√n)”避免溝通成本。很多“高性能”方案其實(shí)都踩過(guò)類似的坑把常見操作的復(fù)雜度降下來(lái)卻忽略了 IO 或輸出量才是真正的瓶頸。這個(gè)問(wèn)題里最后的瓶頸就是輸出本身這絕不是壞事反而說(shuō)明計(jì)算已經(jīng)被優(yōu)化到了幾乎沒有存在感。4.3 大 n 下的表達(dá)式與格式化輸出當(dāng) n 很大比如 10^16你確實(shí)可以用 O(√n) 的時(shí)間把所有平方數(shù)枚舉出來(lái)但直接把它拼成一個(gè)巨大的字符串再一次性打印依然會(huì)引發(fā)內(nèi)存和 IO 問(wèn)題。如果只是要逐行輸出到文件建議流式寫入不要先 build 一個(gè)巨大的數(shù)組。const fs require(fs); const out fs.createWriteStream(lamps.txt); function writeSquareLamps(n) { for (let i 1; i * i n; i) { out.write(String(i * i) \n); } out.end(); }如果你需要的是“第 m 個(gè)亮燈泡是誰(shuí)”那題目就變成了尋找第 m 個(gè)完全平方數(shù)答案就是 m2。此時(shí)連枚舉都不需要直接 O(1) 給出結(jié)果。這也是常數(shù)級(jí)解法的一個(gè)實(shí)際應(yīng)用把“位置”映射到“值”不需要遍歷任何東西。高性能計(jì)算里經(jīng)常有這種操作把枚舉類問(wèn)題翻譯成解析類問(wèn)題讓答案直接從公式里長(zhǎng)出來(lái)。這種思維一旦養(yǎng)成你會(huì)開始習(xí)慣性地尋找問(wèn)題的數(shù)學(xué)結(jié)構(gòu)而不是急著寫循環(huán)。5. 延伸變體從燈泡到更廣的數(shù)學(xué)結(jié)構(gòu)5.1 異或視角與奇偶校驗(yàn)燈泡開關(guān)本質(zhì)上就是二進(jìn)制狀態(tài)的翻轉(zhuǎn)所以它天然和異或運(yùn)算有關(guān)。如果把每盞燈看成一個(gè) bit第 i 輪等價(jià)于把所有 i 的倍數(shù)對(duì)應(yīng)的 bit 異或 1。最終狀態(tài)就是整個(gè)過(guò)程中該 bit 異或 1 的總次數(shù)也就是約數(shù)個(gè)數(shù)的奇偶性。完全平方數(shù)的約數(shù)個(gè)數(shù)為奇因此最終狀態(tài)為 1其他數(shù)為偶最終狀態(tài)為 0。這個(gè)視角在硬件層面很有意思它對(duì)應(yīng)一個(gè)非常輕量的奇偶校驗(yàn)電路你不需要真正構(gòu)建開關(guān)矩陣只需要用約數(shù)奇偶性作為判斷條件。在做低資源嵌入式開發(fā)時(shí)這種“化算力為數(shù)學(xué)”的思路可以省下不少邏輯門數(shù)和存儲(chǔ)空間。我在一個(gè)開源項(xiàng)目里看到過(guò)類似的推廣把“每個(gè)點(diǎn)被訪問(wèn)次數(shù)是否奇數(shù)次”抽象成問(wèn)題直接靠數(shù)學(xué)判斷而不是維護(hù)全局狀態(tài)的往往在數(shù)據(jù)規(guī)模上去后依然能保持極低延遲。這也是“高性能計(jì)算筆記”這個(gè)題目的靈魂用靜態(tài)分析替代動(dòng)態(tài)模擬。5.2 變體問(wèn)題不同翻轉(zhuǎn)頻率與環(huán)形燈泡經(jīng)典題可以輕松改成很多變體。比如只有部分輪次參與操作只翻轉(zhuǎn)編號(hào)為質(zhì)數(shù)的倍數(shù)輪或者燈排成一個(gè)環(huán)每輪翻轉(zhuǎn)固定間隔的燈再或者某些燈一開始就是亮著的需要求最終狀態(tài)。這些變體大多不能直接套用“完全平方數(shù)”結(jié)論但分析套路是相通的先把每盞燈受影響的操作次數(shù)表達(dá)出來(lái)再判斷奇偶性。例如只有第 2、3、5、7... 質(zhì)數(shù)輪參與時(shí)燈號(hào) k 的翻轉(zhuǎn)次數(shù)就是 k 的質(zhì)數(shù)約數(shù)個(gè)數(shù)這時(shí)候就要數(shù) k 的質(zhì)因子族完全平方數(shù)的概念立刻不夠用了。對(duì)大多數(shù)讀者來(lái)說(shuō)掌握基礎(chǔ)版本的推導(dǎo)流程比背誦結(jié)論更有價(jià)值。真正面試或?qū)崙?zhàn)中怪異的變體往往就是把你逼回第一性原理讓你現(xiàn)場(chǎng)從頭推導(dǎo)。能寫出“翻轉(zhuǎn)次數(shù) 約數(shù)個(gè)數(shù) 奇偶性 → 平方數(shù)”這條邏輯鏈的人改一改就能對(duì)付一半變體。6. 常見問(wèn)題與排查技巧實(shí)錄6.1 浮點(diǎn)數(shù) sqrt 與整數(shù)溢出的坑這道題代碼很簡(jiǎn)單但真的動(dòng)手寫細(xì)節(jié)上還有不少暗坑。第一個(gè)坑是用 Math.sqrt 判斷完全平方數(shù)。當(dāng) n 很大時(shí)浮點(diǎn)數(shù)的精度不夠比如 sqrt(10000000000000001) 可能會(huì)被判成整數(shù)導(dǎo)致結(jié)果錯(cuò)誤。正確做法是使用整數(shù)開方函數(shù) isqrt或者自己寫一個(gè)整數(shù)二分。Python 自帶 math.isqrtJavaScript 可以寫一個(gè)簡(jiǎn)單的整數(shù)二分或者先算整數(shù)部分再回乘校驗(yàn)。第二個(gè)坑是枚舉平方數(shù)時(shí)的溢出。如果 n 接近 Number.MAX_SAFE_INTEGERi * i 會(huì)丟精度。在 JavaScript 中可以用 BigInt 或提前判斷 i n / i避免中間結(jié)果越界。下面是安全的判斷方式。function isPerfectSquare(k) { let lo 1, hi k; while (lo hi) { const mid Math.floor((lo hi) / 2); const sq mid * mid; if (sq k) return true; if (sq k) lo mid 1; else hi mid - 1; } return false; }這里最兇險(xiǎn)的地方是 mid * mid 本身也可能溢出。要徹底防止可以改用除法mid k / mid而不是 mid * mid k。這個(gè)小細(xì)節(jié)很多刷題老手也容易漏。6.2 邊界條件與輸出順序第二個(gè)常見的坑是 n 0、n 1 這些邊界值。n 0 時(shí)沒有燈泡答案為空n 1 時(shí)第 1 輪翻轉(zhuǎn)第 1 盞燈亮著答案就是 [1]。用 i * i n 的寫法這兩者天然安全不需要特判。但如果你寫 while (i Math.sqrt(n))浮點(diǎn)誤差可能導(dǎo)致 n 1 時(shí)漏判這是我實(shí)測(cè)見過(guò)的情況。輸出順序也別搞錯(cuò)。枚舉平方數(shù)的時(shí)候自然順序就是從小到大但如果你用哈希集合去重后再輸出反而可能丟失有序性。這道題不需要哈希不需要排序一個(gè) for 循環(huán)就完了別畫蛇添足。6.3 復(fù)雜度分析的口徑還有一個(gè)經(jīng)常被程序員掛在嘴邊的坑把“平均復(fù)雜度”當(dāng)“最壞復(fù)雜度”。如果你對(duì)每個(gè) k 判斷約數(shù)個(gè)數(shù)復(fù)雜度是 O(n√n)比較慢如果你用埃氏篩的思路直接預(yù)處理約數(shù)個(gè)數(shù)復(fù)雜度 O(n log log n) 或 O(n log n)但最優(yōu)做法是避開約數(shù)枚舉用平方數(shù)直出答案復(fù)雜度 O(√n)。三者差別極大討論性能時(shí)一定要說(shuō)清楚你用哪一種。注意如果面試官追問(wèn)“除了完全平方數(shù)還有其他方案嗎”不要慌?？梢韵瘸姓J(rèn)這是最標(biāo)準(zhǔn)的結(jié)論然后提出可以用埃氏篩做預(yù)處理、用直方圖統(tǒng)計(jì)約數(shù)個(gè)數(shù)但最終都會(huì)被數(shù)學(xué)優(yōu)化壓過(guò)。這反而是展示你對(duì)復(fù)雜度和備選方案理解得好機(jī)會(huì)。7. 個(gè)人體會(huì)與建議燈泡開關(guān)問(wèn)題是我見過(guò)最適合用來(lái)練習(xí)“算法思維平移”的小題。它表面上是數(shù)組模擬中間是數(shù)論識(shí)別最后又落回高性能計(jì)算里常說(shuō)的 closed-form 求解。我每次給團(tuán)隊(duì)新人講這道題都會(huì)強(qiáng)調(diào)一句真正的高性能不是代碼寫得有多快而是當(dāng)你發(fā)現(xiàn)這道題根本不需要模擬的時(shí)候代碼里所有優(yōu)化都顯得多余。這幾年的工作里我也經(jīng)常遇到類似的“偽模擬題”。比如某個(gè)數(shù)據(jù)管線的狀態(tài)輪轉(zhuǎn)、某個(gè)游戲里的倍率疊加看起來(lái)要維護(hù)一大堆狀態(tài)其實(shí)只需要把公式推出來(lái)幾個(gè)乘法就結(jié)束了。學(xué)會(huì)識(shí)別這類結(jié)構(gòu)之后你會(huì)從“讀數(shù)據(jù)、換算、輸出”的模式里解放出來(lái)把算力留給真正沒有辦法化簡(jiǎn)的部分。最后再分享一個(gè)小技巧遇到這類“輪轉(zhuǎn)、切換、開關(guān)”的題目第一反應(yīng)永遠(yuǎn)是問(wèn)一句“每個(gè)元素的最終狀態(tài)由什么決定”。如果答案是“被某個(gè)序列命中的次數(shù)”那就果斷把計(jì)數(shù)問(wèn)題拆出來(lái)再用奇偶性、周期、公式去收斂它。燈泡開關(guān)問(wèn)題只是這條思路最清晰、最友好的一個(gè)入門案例但它的思維鏈路會(huì)伴隨你很久。