計算算法的效率和複雜性

-1

我的教練教我們如何計算算法的計算複雜度，但她只這樣做很簡單，不那麼好。更具體地講，可能有人幫我算算下面的計算複雜度：計算算法的效率和複雜性

 While (PLength > 0) 
     chartest = sHex(i) 
     ascvalue = Strings.Asc(chartest) 
     decvalue = Convert.ToDecimal(ascvalue) 
     shiftdecvalue = decvalue + 1 
     asc = ChrW(shiftdecvalue) 
     emptychararray(i) = asc 
     i = i + 1 
     PLength = PLength - 1 
    End While

他們的方式我已經想過這個問題，它只是出來是T（N）= C_1 * N + C_2 *（N -1）+ C_3 *（N-1）+ C_4 *（N-1）+ C_5 *（N-1）+ C_6 *（N-1）+ C_7 *（N-1）+ C_8 *（n-1個）+ C_9 *（N-1）+ C_10 *（N-1）

但我覺得我可能是過於簡單化了。此外，我如何獲得這個大O符號？我一直在網上尋找關於如何教我自己的資源，所以如果你有任何建議，那些將不勝感激。先謝謝你。

來源

2014-04-29 user2016082

你從哪裏得到這麼多條款？你應該把它寫成T（n）=某些包含T（n-c）或T（n/c）的東西。看看其他一些復發關係的例子，你應該做的事情應該變得清楚。同樣，您應該能夠找到大量將重現關係轉換爲大O符號的示例。此外，您需要告訴我們'sHex'，'Strings.Asc'，'Convert.ToDecimal'和'ChrW'與'i'有關的複雜性。 – Dukeling

我的教授教授它的方式是，完成某些操作的每行代碼都被賦予一個常量，然後乘以執行操作的次數。所以我在我的例子中想的是每一行都是完整的n-1次（因爲n取決於執行while循環的次數）。你詢問的項目的複雜性被認爲是一步操作（所以我認爲它們的順序是n）。 – user2016082

首先注意到T（n）的可以改寫爲T(n) = C1 * n + C2。然後請注意，大O符號忽略常量，因此複雜度爲O(n)。

來源

2014-04-29 05:25:32 user3386109

你真的應該解釋你如何得到'T（n）= C1 * n + C2'。如果你想做其他人的功課，你至少應該嘗試詳細解釋它，以便他們能夠找出他們面臨的下一個問題。 – Dukeling

@Dukeling我在等待OP的回覆。在幫助人們理解新概念時，有助於進行對話，以便發現造成混淆源頭的特定點。所以我把這個問題一分爲二，前半部分是從OP的T（n）語句到簡化的T（n）的轉換，後半部分是從簡化的T（n）到大O符號的轉換。 – user3386109

這可能是一個很好的方式來幫助您儘可能少的努力，但是對於其他人的長期價值而言，我認爲最好是足夠詳細地解釋一下，大概是任何人都能理解的，然後修改你的答案，以澄清OP可能有問題的任何點。另外，考慮到OP提出的表達方式，我**強烈懷疑他/她能夠理解你是如何提出你的表達的。 – Dukeling

計算算法的效率和複雜性

回答

相關問題