if-else循環的Big-Oh表示法

鑑於下面的腳本，我需要幫助確定Big-Oh表示法。if-else循環的Big-Oh表示法

p = 0 

if a < b : 

    for i in range(1,n) : 

    j = 1 

    while j < i : 

     p = p + j 

     j = 2 * j 

else : 

    for i in range(1, n) : 

     p = p + 1 

    for j in range(1,n) : 

     p = p + j 

    for k in range(1,n) : 

     p = p + k

這主要是因爲我不確定if和else語句的Big-Oh表示法。我想答案可能只是n，因爲for循環在n的範圍內，但我不確定嵌套的while循環會如何影響答案，或者如果if語句改變它。

來源

2015-08-18 Sharl

我注意到你的一些問題，並且你沒有接受任何答案。你可以接受你認爲有幫助的答案。這給你一些聲譽，所以你可以在這個網站上做更多的事情。你還應該花一點時間看看[旅遊]（http://stackoverflow.com/tour） – AbcAeffchen

由於使用Big-oh表示法，您正在考慮上限，在最壞的情況下應該是O（n * lg n），最好是O（n）。

編輯：我沒有注意到j = j * 2，@AbcAeffchen已經納入。

關於最好的情況和最壞的情況，請看看here。

來源

2015-08-18 10:33:47 Swapnil

最壞的情況和最好的情況究竟意味着什麼？我只知道Big-Oh符號是一個答案？對不起，如果這真的很明顯，也許我還沒有學到它？哈哈 – Sharl

根據輸入a和b：

最好的情況（a ≥ b）：
三環路運行從1到n。所以這是在O(n)。

最壞情況（a < b）：
一個用於運行從1到n循環，具有嵌套的while循環。 while循環具有破壞條件j < i。在while循環中，j總是乘以2，因此j包含的功率爲2。問題是有多大必須x這樣2^x < i成立，答案是log₂ i ≤ log₂ n。所以你得到最壞的情況下O(n⋅log n)。

您發佈的代碼非常簡單，可以找到最佳和最差的情況。如果算法複雜得多，則只能查找最差情況的複雜度。

來源

2015-08-18 14:08:42 AbcAeffchen

if-else循環的Big-Oh表示法

回答

相關問題