hce_nsysu
111年
計算機概論與程式設計
第 51 題
Assume the execution time of a running program is $50(\log n^2) + 8$, then what is the most suitable time complexity?
- A $O(\log n^2)$
- B $O((\log n)^2)$
- C $O(\log n)$
- D $O(n)$
- E $O(n^2)$
思路引導 VIP
當你在評估一個包含對數的函數時，如果發現真數（即對數括號內的值）帶有次方（例如 $\log n^k$），根據數學運算性質，這個次方可以移動到對數的前面變成什麼？而在計算大 O 符號時，這種移動後的結果會被如何處理呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地選出了正確答案！你能一眼看穿題目中的數學陷阱，代表你對大 O 符號（Big O notation）的定義以及對數運算性質都有著非常紮實的理解，這在處理演算法效率分析時是非常關鍵的能力。
對數性質與大 O 符號的簡化
這道題目的核心在於對數律的運用。執行時間函數為 $50(\log n^2) + 8$，根據對數性質 $\log(a^b) = b \cdot \log a$，我們可以將 $\log n^2$ 轉換為 $2 \log n$。如此一來，原式便可改寫為：
▼ 還有更多解析內容