跳至主要內容
OCME中英數學知識與推導English

OCME · 中英數學知識與推導

概念推導導讀

299 份概念教學導讀;另有 36,000 題逐題詳解,兩者分開查找。

搜尋全部題目與詳解 →

概念導讀

漸近資源界:證明 3n²+5n+2∈Θ(n²) 並排除 Θ(n)

設成本函數 f(n)=3n²+5n+2(n 從 0 起),比較函數 g(n)=n² 與 h(n)=n。以明示的全尾段 witness 證明 f∈O(g)(c=10、N=1)、f∈Ω(g)(c=3、N=0),故 f∈Θ(g);說明 N=0 對 O 不可行、c=3 對 O 不可行、另一組 witness c=4、N=6 也可行;再證明 f∉O(h),因此 f∈Ω(h) 但 f∉Θ(h)。

漸近資源界

derivation-mko-asymptotic-resource-bound-01