asymptotic-complexity

2熱度

2回答

是否存在複雜度爲O（1）而不是用於addAll操作的O（n）的Java集合，還是必須實現自己的集合？使用高效的鏈接列表，Collection1.addAll（Collection2）操作應該將第二個集合附加到第一個將collection2的第一個節點添加到集合1的最後一個節點，其他節點遵循。但這並不是說我讀到了似乎使用Iterator的文檔，所以我想複雜度是O（collection2.size）。

-3熱度

1回答

中的特定功能的最壞的情況下（O（N））確定的漸近複雜

我想確定在最壞情況下的漸近複雜下面的函數： int j; float r = 1.0; for (int i=1; i<(log n); i++){ j = 1; while (j <= i^2){ r*=2; j++; } print(r);

3熱度

1回答

最長的子串沒有重複的人物角落案件

我在最近的一次採訪中被問到這個問題。我需要找到最長的substring而不重複字符。鑑於「abcabcbb」，答案是「abc」，其長度爲3 賦予「bbbbb」，答案是「b」，用的1 鑑於長度「 pwwkew」，答案是‘wke’，用3 長度。這是我想出了，我覺得它工作正常，但面試官沒有留下深刻印象，說我的解決方案可能不適合所有情況。 var str = "pwwkew"; v

3熱度

1回答

爲什麼pop_heap的複雜性是O（2 * log（N））？

我在幾個地方看到，在priority_queue中，pop_heap的複雜度是O（2 * log（N）），這是真的嗎？如果是，那2個來自哪裏？刪除第一個元素後，它只需要重建堆，這將花費O（log（N））。

0熱度

1回答

計算複雜度以外的其他時空資源

一般來說，在計算複雜度上，我們討論的是時間和空間的複雜性。也就是說，我們考慮解決某些問題需要多少時間或空間。我想知道是否有另一種資源（超越時間和空間），我們可以使用參考來討論計算複雜性。

1熱度

1回答

最壞情況下的時間複雜度

未排序的n個數字列表，找到列表中具有最小差異的任意兩個數字。如果我必須爲此寫一個算法，最壞的情況是O(nlogn)。以下算法的工作可以：使用合併排序遍歷整個列表一次，排序列表中找到連續數字之間的差異。具有最小差異的退貨號碼。這種算法的時間複雜性是：O(nlogn + n)，我可以這麼說O(nlogn)？

1熱度

2回答

是否arr = [val] * N具有班輪或恆定時間？

我正在努力解決一些編碼問題。我想知道answ = [max] * N是線性還是恆定時間？ def solution(N, A): answ = [0] * N max = 0 for item in A: if item > N: answ = [max] * N # this line here. Linear or constant

1熱度

2回答

漸進複雜度std :: remove_if

我正在研究數據結構的擦除方法，該數據結構具有硬編碼的最大元素數N，它依賴於std::array來避免堆內存。雖然std::array包含N個元素只有一些數目M，都是「相關的」元素，其中M小於或等於N.作爲一個例子，如果N是10和陣列看起來像這樣： std::array<int, N> elements = { 0, 1, 2, -1, 4, -1, 6, -1, -1, 9 }; ...如果M

1熱度

1回答

分部的複雜性

文章Computational complexity of mathematical operations提到O(M(n))的劃分的複雜性，以及下面的「M(n)」代表了所選乘法算法的複雜性。但我不知道如何讀取M(n)嵌入O(M(n))：這是否意味着該分區具有與乘法相同的複雜性？如果我使用Karatsuba乘法算法，請問該師還會採用O(n^1.585)？

1熱度

1回答

如何在Python中輸入數據時保留排序列表

我有一個列表，需要根據列表的長度對列表進行排序。我現在所做的是首先將列表插入主列表，然後對給出key=len的主列表進行排序。此步驟總共需要n + nlg(n)。將數據輸入到主列表中時是否可以維護排序列表？它可以使用平分線（或有更好的方法），如果是的話，它會比n + nlg(n)更好嗎？