《Hello 算法》計算複雜度章節練習全解析迭代、遞迴與時間空間複雜度實戰【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇文章以《Hello 算法》繁體中文版「計算複雜度」章節的章末練習為核心逐題拆解知識鞏固與程式設計練習的完整思路並結合倉庫內 Python、C、C、Java、Go、JavaScript 等 14 種語言的習題原始碼與測試用例說明如何從執行過程推導時間複雜度與空間複雜度。讀完本篇你將掌握「迭代 vs 遞迴」的效率對比、常數/線性/平方/對數階的辨識方法、原地操作in-place的空間代價以及用迴圈實現費波那契數列的迭代技巧。題目總覽與學習路徑章末練習共分兩大部分、四道題全部圍繞「複雜度分析」這一核心主題題目類型考察重點迭代與遞迴的時間和空間知識鞏固追蹤執行過程對比 $O(n)$ 時間下 $O(1)$ 與 $O(n)$ 空間的差異三段程式碼的時間複雜度知識鞏固辨識線性階、平方階與對數階並按漸進複雜度排序哪種反轉更節省空間知識鞏固空間複雜度與「原地」操作的取捨費波那契數程式設計練習用迴圈迭代實現 $F(n)$不使用遞迴其中前三題的函式均已收錄於倉庫的complexity_exercises系列檔案中例如 C 語言版、Python 版、C 版、Java 版 等讀者可以在本地直接編譯執行驗證第四題則需要自行完成實作。第一題迭代與遞迴的時間和空間題目與程式碼題目要求對比「計算 $1 2 \dots n$$n \ge 1$」的兩種寫法迭代版sumIter與遞迴版sumRecur並在n 4時逐步追蹤執行過程。以 C 語言實現為例/* 迭代求和 */ int sumIter(int n) { int res 0; for (int i 1; i n; i) { res i; } return res; } /* 遞迴求和 */ int sumRecur(int n) { if (n 1) { return 1; } return n sumRecur(n - 1); }兩種寫法在其他語言中保持了完全一致的邏輯Python 版sum_iter/sum_recur見 complexity_exercises.py、Go 版sumIter/sumRecur見 complexity_exercises.go。這也體現了《Hello 算法》「一鍵運行、多語言對照」的設計理念。追蹤迭代版res 的變化過程設n 4迴圈變數i依次取1、2、3、4每輪結束後累加變數res依次變為第 1 輪res 0 1 1第 2 輪res 1 2 3第 3 輪res 3 3 6第 4 輪res 6 4 10因此迭代函式返回 10。此過程對應的正是迭代章節中描述的「自下而上」求解從最基礎的步驟開始反覆累加直至任務完成。追蹤遞迴版參數的取值與回溯設n 4遞迴呼叫鏈為sumRecur(4) → sumRecur(3) → sumRecur(2) → sumRecur(1)參數n依次取4 → 3 → 2 → 1。到達終止條件n 1後開始逐層返回「迴」的階段最深層sumRecur(1)返回1sumRecur(2)得到2 1 3sumRecur(3)得到3 3 6sumRecur(4)得到4 6 10。關鍵在於在最深處4 次函式呼叫都尚未結束。這正是遞迴章節所講的「呼叫堆疊」——遞迴函式每次呼叫自身時系統都會為新開啟的函式分配記憶體儲存區域性變數與呼叫位址直至函式返回後才釋放。效率對比與複雜度分析維度迭代版sumIter遞迴版sumRecur時間複雜度$O(n)$$O(n)$空間複雜度$O(1)$$O(n)$時間複雜度兩段程式碼都進行與 $n$ 成正比的迴圈或呼叫操作數量均為 $O(n)$ 量級空間複雜度核心區別迭代版只使用常數個變數res、i空間為 $O(1)$遞迴版在到達終止條件前前面的函式呼叫都要等待返回結果呼叫堆疊中最多同時儲存 $n$ 次呼叫因此空間複雜度為 $O(n)$。這裡有一個易錯點值得強調分析空間複雜度時除程式碼中的變數外還要考慮遞迴呼叫佔用的堆疊空間。正如遞迴章節指出的遞迴通常比迭代更耗費記憶體且函式呼叫本身有額外開銷因此時間效率通常也更低若遞迴過深甚至可能觸發堆疊溢位。第二題三段程式碼的時間複雜度排序題目與程式碼題目給出三個以正整數 $n$ 為輸入的程式片段要求按時間複雜度從低到高排序。倉庫中的三個函式實現如下C 版/* 線性階迴圈 */ int linearLoop(int n) { int res 0; for (int i 0; i n; i) { res i; } return res; } /* 平方階迴圈 */ int quadraticLoop(int n) { int res 0; for (int i 0; i n; i) { for (int j i; j n; j) { res j; } } return res; } /* 對數階迴圈 */ int logarithmicLoop(int n) { while (n 1) { n / 2; } return n; }逐一推導複雜度片段一線性階 $O(n)$迴圈恰好執行 $n$ 次每次操作量為常數總操作數量與 $n$ 成正比片段二平方階 $O(n^2)$內層迴圈次數依次為 $n, n-1, \dots, 1$總執行次數為 $\frac{n(n1)}{2}$因此屬於平方階。注意它是一個「三角形迴圈」雖然係數是 $1/2$但在漸進分析中常數因子被忽略仍記為 $O(n^2)$對應迭代章節中「巢狀迴圈每一次巢狀都是一次升維」的論述片段三對數階 $O(\log n)$每輪把 $n$ 縮小為原來的一半約迴圈 $\log_2 n$ 次屬於對數階。最終答案按時間複雜度從低到高排列片段三 $O(\log n)$ 片段一 $O(n)$ 片段二 $O(n^2)$。這三種階別的圖形化直觀對比可參考時間複雜度章節中對漸進增長率的分析對數階增長最慢線性階居中平方階增長最快。第三題哪種反轉更節省空間題目描述要將陣列nums中的元素全部反轉有兩種做法新建等長陣列res倒序複製原陣列後返回雙索引原地交換用索引i、j分別從首、尾向中間移動逐對交換nums[i]與nums[j]。複雜度與「原地」判定做法空間複雜度是否原地方法一新建陣列$O(n)$否方法二雙索引交換$O(1)$是方法一需要與輸入等長的輔助陣列空間複雜度 $O(n)$方法二只使用兩個索引變數空間複雜度 $O(1)$屬於「原地in-place」操作。重要的取捨結論需要注意原地反轉會修改輸入陣列僅在允許修改輸入時才應優先選用。若後續邏輯仍需使用原始陣列方法一的複製開銷就不可避免。這道題的深層含義是空間複雜度分析不能脫離業務約束——「省空間」與「保留原資料」往往是魚與熊掌的關係工程中需要根據場景權衡。程式設計練習用迴圈實現費波那契數題目要求費波那契數列滿足 $F(0)0$、$F(1)1$且當 $n\ge2$ 時 $F(n)F(n-1)F(n-2)$。給定非負整數n請使用迴圈計算並返回 $F(n)$不使用遞迴。解題思路與提示解讀原題給出三條關鍵提示對應著迭代實作的三大要點先單獨處理n為 0 和 1 的情況這是迴圈無法覆蓋的邊界迴圈至少需要從第 2 項開始疊代計算下一項時只需要前兩項無須儲存整個數列這保證了空間複雜度為 $O(1)$——我們不需要一個長度為 $n1$ 的陣列更新兩個變數時注意不要過早覆蓋仍會用到的舊值例如先計算next a b再依序更新a b; b next順序顛倒就會丟失資料。參考實作Pythondef fibonacci(n: int) - int: 迴圈實作費波那契數列不使用遞迴 if n 0: return 0 if n 1: return 1 a, b 0, 1 # 只保留前兩項 for _ in range(2, n 1): a, b b, a b # 同時更新避免舊值被覆蓋 return b複雜度分析時間複雜度 $O(n)$迴圈恰好執行 $n-1$ 次與 $n$ 成正比空間複雜度 $O(1)$全程只使用常數個變數a、b無須額外陣列也無須遞迴堆疊。對比之下樸素的遞迴寫法F(n) F(n-1) F(n-2)時間複雜度高達 $O(2^n)$且堆疊深度為 $O(n)$——這正是動態規劃章節所要解決的核心問題。本練習讓讀者以最直觀的方式體驗「用空間換時間」與「用迭代消除重複計算」的價值。如何在本機驗證答案倉庫為前三道題提供了完整的可執行程式碼與測試可直接在本機執行驗證C 語言complexity_exercises.c已登記在 chapter_computational_complexity/CMakeLists.txt 中執行add_executable(complexity_exercises complexity_exercises.c)後即可編譯運行main函式內含多條assert例如sumIter(4) 10 sumRecur(4) 10、quadraticLoop(4) 20、logarithmicLoop(4) 1 logarithmicLoop(5) 1全部通過即代表答案正確Go 語言提供了獨立的單元測試檔案 complexity_exercises_test.go覆蓋n 1與n 4兩種輸入下求和函式的正確性以及三個複雜度迴圈函式的輸出值Python / Java / C / JavaScript等版本同樣內建了assert或拋錯式檢查例如 JavaScript 版在任一斷言失敗時會拋出complexity exercise check failed。讀者可先手算題目答案再透過這些測試快速核對完成「理解概念 → 手動推導 → 程式驗證」的閉環。小結迭代與遞迴都能求解同一問題但效率不同時間同為 $O(n)$ 時迭代空間 $O(1)$、遞迴空間 $O(n)$且遞迴有額外呼叫開銷時間複雜度的本質是操作數量的漸進增長率能從循環結構直接辨識線性階 $O(n)$、平方階 $O(n^2)$、對數階 $O(\log n)$並正確排序「原地」不是免費的$O(1)$ 空間的原地操作以修改輸入為代價需視業務是否允許修改輸入而定迭代可以替代遞迴費波那契數列的迴圈實作體現了「只保留必要狀態」的迭代思維兼得 $O(n)$ 時間與 $O(1)$ 空間。如需深入背景知識可繼續閱讀同章節的迭代與遞迴、時間複雜度與空間複雜度正文並配合倉庫內 codes/c/chapter_computational_complexity 目錄下的原始碼反覆練習。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 《Hello 算法》計算複雜度章節練習全解析：迭代、遞迴與時間空間複雜度實戰
《Hello 算法》計算複雜度章節練習全解析迭代、遞迴與時間空間複雜度實戰【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇文章以《Hello 算法》繁體中文版「計算複雜度」章節的章末練習為核心逐題拆解知識鞏固與程式設計練習的完整思路並結合倉庫內 Python、C、C、Java、Go、JavaScript 等 14 種語言的習題原始碼與測試用例說明如何從執行過程推導時間複雜度與空間複雜度。讀完本篇你將掌握「迭代 vs 遞迴」的效率對比、常數/線性/平方/對數階的辨識方法、原地操作in-place的空間代價以及用迴圈實現費波那契數列的迭代技巧。題目總覽與學習路徑章末練習共分兩大部分、四道題全部圍繞「複雜度分析」這一核心主題題目類型考察重點迭代與遞迴的時間和空間知識鞏固追蹤執行過程對比 $O(n)$ 時間下 $O(1)$ 與 $O(n)$ 空間的差異三段程式碼的時間複雜度知識鞏固辨識線性階、平方階與對數階並按漸進複雜度排序哪種反轉更節省空間知識鞏固空間複雜度與「原地」操作的取捨費波那契數程式設計練習用迴圈迭代實現 $F(n)$不使用遞迴其中前三題的函式均已收錄於倉庫的complexity_exercises系列檔案中例如 C 語言版、Python 版、C 版、Java 版 等讀者可以在本地直接編譯執行驗證第四題則需要自行完成實作。第一題迭代與遞迴的時間和空間題目與程式碼題目要求對比「計算 $1 2 \dots n$$n \ge 1$」的兩種寫法迭代版sumIter與遞迴版sumRecur並在n 4時逐步追蹤執行過程。以 C 語言實現為例/* 迭代求和 */ int sumIter(int n) { int res 0; for (int i 1; i n; i) { res i; } return res; } /* 遞迴求和 */ int sumRecur(int n) { if (n 1) { return 1; } return n sumRecur(n - 1); }兩種寫法在其他語言中保持了完全一致的邏輯Python 版sum_iter/sum_recur見 complexity_exercises.py、Go 版sumIter/sumRecur見 complexity_exercises.go。這也體現了《Hello 算法》「一鍵運行、多語言對照」的設計理念。追蹤迭代版res 的變化過程設n 4迴圈變數i依次取1、2、3、4每輪結束後累加變數res依次變為第 1 輪res 0 1 1第 2 輪res 1 2 3第 3 輪res 3 3 6第 4 輪res 6 4 10因此迭代函式返回 10。此過程對應的正是迭代章節中描述的「自下而上」求解從最基礎的步驟開始反覆累加直至任務完成。追蹤遞迴版參數的取值與回溯設n 4遞迴呼叫鏈為sumRecur(4) → sumRecur(3) → sumRecur(2) → sumRecur(1)參數n依次取4 → 3 → 2 → 1。到達終止條件n 1後開始逐層返回「迴」的階段最深層sumRecur(1)返回1sumRecur(2)得到2 1 3sumRecur(3)得到3 3 6sumRecur(4)得到4 6 10。關鍵在於在最深處4 次函式呼叫都尚未結束。這正是遞迴章節所講的「呼叫堆疊」——遞迴函式每次呼叫自身時系統都會為新開啟的函式分配記憶體儲存區域性變數與呼叫位址直至函式返回後才釋放。效率對比與複雜度分析維度迭代版sumIter遞迴版sumRecur時間複雜度$O(n)$$O(n)$空間複雜度$O(1)$$O(n)$時間複雜度兩段程式碼都進行與 $n$ 成正比的迴圈或呼叫操作數量均為 $O(n)$ 量級空間複雜度核心區別迭代版只使用常數個變數res、i空間為 $O(1)$遞迴版在到達終止條件前前面的函式呼叫都要等待返回結果呼叫堆疊中最多同時儲存 $n$ 次呼叫因此空間複雜度為 $O(n)$。這裡有一個易錯點值得強調分析空間複雜度時除程式碼中的變數外還要考慮遞迴呼叫佔用的堆疊空間。正如遞迴章節指出的遞迴通常比迭代更耗費記憶體且函式呼叫本身有額外開銷因此時間效率通常也更低若遞迴過深甚至可能觸發堆疊溢位。第二題三段程式碼的時間複雜度排序題目與程式碼題目給出三個以正整數 $n$ 為輸入的程式片段要求按時間複雜度從低到高排序。倉庫中的三個函式實現如下C 版/* 線性階迴圈 */ int linearLoop(int n) { int res 0; for (int i 0; i n; i) { res i; } return res; } /* 平方階迴圈 */ int quadraticLoop(int n) { int res 0; for (int i 0; i n; i) { for (int j i; j n; j) { res j; } } return res; } /* 對數階迴圈 */ int logarithmicLoop(int n) { while (n 1) { n / 2; } return n; }逐一推導複雜度片段一線性階 $O(n)$迴圈恰好執行 $n$ 次每次操作量為常數總操作數量與 $n$ 成正比片段二平方階 $O(n^2)$內層迴圈次數依次為 $n, n-1, \dots, 1$總執行次數為 $\frac{n(n1)}{2}$因此屬於平方階。注意它是一個「三角形迴圈」雖然係數是 $1/2$但在漸進分析中常數因子被忽略仍記為 $O(n^2)$對應迭代章節中「巢狀迴圈每一次巢狀都是一次升維」的論述片段三對數階 $O(\log n)$每輪把 $n$ 縮小為原來的一半約迴圈 $\log_2 n$ 次屬於對數階。最終答案按時間複雜度從低到高排列片段三 $O(\log n)$ 片段一 $O(n)$ 片段二 $O(n^2)$。這三種階別的圖形化直觀對比可參考時間複雜度章節中對漸進增長率的分析對數階增長最慢線性階居中平方階增長最快。第三題哪種反轉更節省空間題目描述要將陣列nums中的元素全部反轉有兩種做法新建等長陣列res倒序複製原陣列後返回雙索引原地交換用索引i、j分別從首、尾向中間移動逐對交換nums[i]與nums[j]。複雜度與「原地」判定做法空間複雜度是否原地方法一新建陣列$O(n)$否方法二雙索引交換$O(1)$是方法一需要與輸入等長的輔助陣列空間複雜度 $O(n)$方法二只使用兩個索引變數空間複雜度 $O(1)$屬於「原地in-place」操作。重要的取捨結論需要注意原地反轉會修改輸入陣列僅在允許修改輸入時才應優先選用。若後續邏輯仍需使用原始陣列方法一的複製開銷就不可避免。這道題的深層含義是空間複雜度分析不能脫離業務約束——「省空間」與「保留原資料」往往是魚與熊掌的關係工程中需要根據場景權衡。程式設計練習用迴圈實現費波那契數題目要求費波那契數列滿足 $F(0)0$、$F(1)1$且當 $n\ge2$ 時 $F(n)F(n-1)F(n-2)$。給定非負整數n請使用迴圈計算並返回 $F(n)$不使用遞迴。解題思路與提示解讀原題給出三條關鍵提示對應著迭代實作的三大要點先單獨處理n為 0 和 1 的情況這是迴圈無法覆蓋的邊界迴圈至少需要從第 2 項開始疊代計算下一項時只需要前兩項無須儲存整個數列這保證了空間複雜度為 $O(1)$——我們不需要一個長度為 $n1$ 的陣列更新兩個變數時注意不要過早覆蓋仍會用到的舊值例如先計算next a b再依序更新a b; b next順序顛倒就會丟失資料。參考實作Pythondef fibonacci(n: int) - int: 迴圈實作費波那契數列不使用遞迴 if n 0: return 0 if n 1: return 1 a, b 0, 1 # 只保留前兩項 for _ in range(2, n 1): a, b b, a b # 同時更新避免舊值被覆蓋 return b複雜度分析時間複雜度 $O(n)$迴圈恰好執行 $n-1$ 次與 $n$ 成正比空間複雜度 $O(1)$全程只使用常數個變數a、b無須額外陣列也無須遞迴堆疊。對比之下樸素的遞迴寫法F(n) F(n-1) F(n-2)時間複雜度高達 $O(2^n)$且堆疊深度為 $O(n)$——這正是動態規劃章節所要解決的核心問題。本練習讓讀者以最直觀的方式體驗「用空間換時間」與「用迭代消除重複計算」的價值。如何在本機驗證答案倉庫為前三道題提供了完整的可執行程式碼與測試可直接在本機執行驗證C 語言complexity_exercises.c已登記在 chapter_computational_complexity/CMakeLists.txt 中執行add_executable(complexity_exercises complexity_exercises.c)後即可編譯運行main函式內含多條assert例如sumIter(4) 10 sumRecur(4) 10、quadraticLoop(4) 20、logarithmicLoop(4) 1 logarithmicLoop(5) 1全部通過即代表答案正確Go 語言提供了獨立的單元測試檔案 complexity_exercises_test.go覆蓋n 1與n 4兩種輸入下求和函式的正確性以及三個複雜度迴圈函式的輸出值Python / Java / C / JavaScript等版本同樣內建了assert或拋錯式檢查例如 JavaScript 版在任一斷言失敗時會拋出complexity exercise check failed。讀者可先手算題目答案再透過這些測試快速核對完成「理解概念 → 手動推導 → 程式驗證」的閉環。小結迭代與遞迴都能求解同一問題但效率不同時間同為 $O(n)$ 時迭代空間 $O(1)$、遞迴空間 $O(n)$且遞迴有額外呼叫開銷時間複雜度的本質是操作數量的漸進增長率能從循環結構直接辨識線性階 $O(n)$、平方階 $O(n^2)$、對數階 $O(\log n)$並正確排序「原地」不是免費的$O(1)$ 空間的原地操作以修改輸入為代價需視業務是否允許修改輸入而定迭代可以替代遞迴費波那契數列的迴圈實作體現了「只保留必要狀態」的迭代思維兼得 $O(n)$ 時間與 $O(1)$ 空間。如需深入背景知識可繼續閱讀同章節的迭代與遞迴、時間複雜度與空間複雜度正文並配合倉庫內 codes/c/chapter_computational_complexity 目錄下的原始碼反覆練習。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考