3 回答

TA貢獻(xiàn)1942條經(jīng)驗(yàn) 獲得超3個(gè)贊
如何找到算法的時(shí)間復(fù)雜度
您可以根據(jù)輸入的大小計(jì)算它將執(zhí)行多少個(gè)機(jī)器指令,然后將表達(dá)式簡化為最大(當(dāng)N非常大)時(shí),可以包含任何簡化常量因子。
例如,讓我們看看我們?nèi)绾魏喕?code>2N + 2機(jī)器指令來描述它O(N)
。
我們?yōu)槭裁匆獎(jiǎng)h除這兩個(gè)2
?
當(dāng)N變大時(shí),我們對(duì)算法的性能感興趣。
考慮兩個(gè)術(shù)語2N和2。
當(dāng)N變大時(shí),這兩個(gè)術(shù)語的相對(duì)影響是什么?假設(shè)N是一百萬。
然后第一個(gè)詞是200萬,第二個(gè)詞只有2。
出于這個(gè)原因,我們放棄了大N的最大條件。
所以,現(xiàn)在我們已經(jīng)離開2N + 2
了2N
。
傳統(tǒng)上,我們只對(duì)恒定因素的表現(xiàn)感興趣。
這意味著當(dāng)N很大時(shí),我們并不在乎是否存在性能差異的恒定倍數(shù)。無論如何,2N的單位首先沒有明確定義。因此,我們可以乘以或除以常數(shù)因子來得到最簡單的表達(dá)式。
所以2N
變得公正N
。
添加回答
舉報(bào)