asymptotic-complexity

1熱度

1回答

爲什麼同一個方程給出不同的大O值

在演講幻燈片中呈現的一個例子中，大分析讓我很困惑。它指出：2N^2 + 4N = O（N^2）和2N^2 + 4N = O（N^4）有人能解釋中相同的方程如何產生不同的結果？謝謝

2熱度

1回答

你會如何在哪一種算法優於另一種算法

我想比較兩種算法及其大哦效率。我試圖找到n的值，其中一種算法比另一種算法更有效。任何有用的例子或資源將是一個巨大的幫助。

3熱度

1回答

最糟糕的shell排序方案：Θ（N^3/2）或O（（NlogN）^ 2）？

我正在尋找殼牌排序的最壞情況。根據this，最壞的情況是O(N^3/2) 但是here，聲稱最壞的情況是O((N log N)^2))。我認爲最壞的情況應該是一個包含奇數位置最大值的序列。然而，一些間隙序列與Θ(N^3/2)複雜性一起引入。我想弄清楚什麼是殼牌排序的實際最壞情況。到目前爲止，根據上述文件，最壞的情況是O((N log N)^2))而不是Θ(N^3/2)。另外，here提出了一

0熱度

1回答

如何解決如$ T（n）= T（n/2）+ T（n/4）+ O（m）這樣的遞歸關係$

我希望得到這個再發生的更嚴格的界限，兩個變量m和n。

1熱度

2回答

如果f（n）是歐米茄（g（n）），那麼2 ^（f（n））是歐米茄（2^g（n））。這是真的還是假的

對於這個問題，我想是因爲我認爲這個問題基本上是問f(n)大於或等於g(n)則比2^(f(n))大於或等於2^(g(n)) 因此，如果我們拿一個實例是真的f(n) = 2n和g(n) = n,f(n)是> g(n)。然後2^2n大於2^n。但我的朋友說這不正確，有人能給我一些見解嗎？我想我可能會對這個問題有所誤解。

-2熱度

1回答

循環的漸近運行時間

function func5(n) s = 0; for i = 1 to 3n^2 do for j = 1 to floor(2n^3/i) do s=s + i − j; return(s); 上述算法在theta符號中的漸近運行時間是多少？

0熱度

1回答

解決這個重複沒有主定理。回溯算法

我做了一個回溯算法。我被要求說這個Algo的複雜性。我知道方程是T（n）= 2T（n-1）+3（n_hat），其中n_hat是最初的n。這意味着每一步都不會減少。事情是，我在計算這個東西時感到很失落。我相信它大概是2 ** n *。但是我的計算有點混亂。你能幫我嗎？謝謝！

0熱度

2回答

從排序後的數組創建BST的大哦

我已經寫了這種方法來將我有的排序數組轉換爲平衡二叉搜索樹。我不確定這種方法的大時間複雜性應該是什麼。它會是O（n）嗎？ Node ArrayToBST(Node arr[], int start, int end) { if (start > end) return null; int mid = (start + end)/2; Node node =

0熱度

3回答

這段短代碼的運行時複雜度是多少？

我在編程練習網站上找到了這個解決方案，它說複雜性是O（N）。但是，它對我來說更像O（N^2）。有人可以告訴我爲什麼這是O（N）嗎？ public static void transposeMatrix(int[][] matrix) { int n = matrix.length - 1; int temp = 0; for(int i = 0; i <= n; i+

0熱度

1回答

什麼時候使用大O而不是theta或小o

關於漸近表示法的問題。我見過很多漸近記法的解釋說： θ(...)類似於= O(...)類似於<= o(...)類似於< 這似乎暗示如果是f(n) = O(g(n))，則可以是f(n) = θ(g(n))或f(n) = o(g(n))。是否有可能讓f(n) = O(g(n))這樣既不f(n) = θ(g(n))和f(n) = o(g(n))？如果是這樣，這是什麼例子？如果不是，那麼爲什麼我們會使用