如何找到算法的時間復雜度問題如何找到算法的時間復雜度?在SO上發布問題之前我做了什么?我走過了這個,這和許多其他鏈接但是,我無法找到關于如何計算時間復雜度的明確而直接的解釋。我知道什么 ?假設代碼如下所示:char h = 'y'; // This will be executed 1 timeint abc = 0; // This will be executed 1 time說一個像下面這樣的循環:for (int i = 0; i < N; i++) {
Console.Write('Hello World !');}int i = 0; 這只會執行一次。時間實際上是計算i=0而不是聲明。我<N; 這將執行N + 1次i ++; 這將被執行N次所以這個循環所需的操作數量是{1+(N + 1)+ N} = 2N + 2注意:這仍然可能是錯誤的,因為我對計算時間復雜度的理解沒有信心我想知道什么?好吧,所以這些小基本計算我想我知道,但在大多數情況下,我已經看到了時間復雜度O(N),O(N2),O(log n)的,為O(n?。?nbsp;......和許多其他,任何人都可以幫我理解如何計算算法的時間復雜度?我相信有很多像我這樣的新手想知道這件事。
3 回答

手掌心
TA貢獻1942條經驗 獲得超3個贊
如何找到算法的時間復雜度
您可以根據輸入的大小計算它將執行多少個機器指令,然后將表達式簡化為最大(當N非常大)時,可以包含任何簡化常量因子。
例如,讓我們看看我們如何簡化2N + 2
機器指令來描述它O(N)
。
我們為什么要刪除這兩個2
?
當N變大時,我們對算法的性能感興趣。
考慮兩個術語2N和2。
當N變大時,這兩個術語的相對影響是什么?假設N是一百萬。
然后第一個詞是200萬,第二個詞只有2。
出于這個原因,我們放棄了大N的最大條件。
所以,現在我們已經離開2N + 2
了2N
。
傳統上,我們只對恒定因素的表現感興趣。
這意味著當N很大時,我們并不在乎是否存在性能差異的恒定倍數。無論如何,2N的單位首先沒有明確定義。因此,我們可以乘以或除以常數因子來得到最簡單的表達式。
所以2N
變得公正N
。
添加回答
舉報
0/150
提交
取消