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