big-o

2熱度

1回答

那麼，我想弄清楚循環中的大O運行時。我有答案，但我想檢查一下社區。 m =1; 1 for (i = 1; i <= n; i++) n+1 for (j = 1; j <= n*n; j++) n(n+1) = n^2+n for (k = 1; k <= n*n*n; k++) n(n^2+

0熱度

1回答

平均案例大O和排序的影響

我正在研究確定String是否包含所有唯一字符的方法實現的時間複雜性。基本，蠻力，方法是在同一時間通過String一個字符來迭代保持的HashSet看到字符。對於迭代中的每個字符，我們檢查Set是否已經包含它，如果是，則返回false。如果搜索到整個String，則返回true。作爲最壞情況的複雜度，這將是O(n)。平均情況是什麼？ O(n/2)？如果我們試圖通過將String排序爲char數

0熱度

1回答

哈希表O（1）攤銷或O（1）平均攤銷？

這個問題看起來有些迂腐，但我一直在努力深入研究Amortized分析，並且對於爲什麼插入一個哈希表是O（1）分期付款有點困惑（注意：我不是在談論表加倍，我明白）使用此定義，「攤銷分析給出了在最差情況下每項操作的平均性能（隨時間變化）。」看起來N個插入散列表的最壞情況會導致每個操作的衝突。我相信當負載平衡保持較低時，通用散列保證以1/m的速率發生碰撞，但是在理論上每個插入點都可能碰撞嗎？好像技術

-3熱度

1回答

在這些情況下有什麼不同？

在這兩個不同的代碼（做同樣的事情），是bigO不同。 O（1）語句已更改，但for循環保持相同，即運行次數相同？ for (i=0;i<n;i++) { for (j=0;j<i;j++) { b+=i+i } } 而且， for (i=0;i<n;i++) { int k = i+i; for (j=0;j<i;j++) {

0熱度

1回答

比較不同輸入的運行時間/減少大O幅度和不同功能的輸入

我對大O表示法的某些方面有些困惑。我提前爲這個複雜的例子道歉如果一個函數ex。 O(2^N) + O(N^7); N輸入值被認爲是相同的，並且O(N^7)將主導O(2^N)或者大O幅度可以減少到O(N^7)。 O(2^N) * O(N^7)也是如此; O(N^7)將主導，因爲N（或輸入）的值被認爲是相同的，並且運行時間比O(2^N)更差。一個函數需要有兩個輸入值，這些值可以用一個函數來表示爲O(

-1熱度

3回答

3個嵌套for循環的大O？

public int Loop(int[] array1) { int result = 0; for (int i = 0; i < array1.length; i++) { for (int j = 0; j < array1.length; j++) { for (int k = 1; k < array1.length; k = k

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))？如果是這樣，這是什麼例子？如果不是，那麼爲什麼我們會使用

-4熱度

2回答

爲什麼主定理不能適用

做一個任務，並被困在了幾個問題。 T（N）= T（2π/ 5）+ N T（N）= T（2π/ 3）+ T（N/3）+ N T（N）= T（n-2）+ n 有些東西告訴我他們所有的定理都不能應用。但爲什麼？他們的上限是什麼（大哦）？

1熱度

1回答

兩個代碼片段的大O符號

我已經有兩段代碼和他們所屬的大O類別的解釋。然而，儘可能地嘗試一下，我無法通過觀察它或者進行樣品運行來得出解釋。第一： long count = 0; long n = 1000; long i, j, k; for(i = 0; i < n; i++) for (j = 0; j < i * i; j++) for (k = 0; k < j; k++)

0熱度

2回答

運行時間複雜度

我相信下面的代碼是n^3的大的theta，這是正確的嗎？ for (int i = 0; i < n; i ++) { // A is an array of integers if (A[i] == 0) { for (int j = 0; j <= i; j++) { if (A[i] == 0) { for (int k = 0; k <=