complexity-theory

0熱度

1回答

問：Python3中random.choice（list）的Big-O複雜度是什麼

什麼是Python3中random.choice（list）的Big-O複雜度，其中n是列表中元素的數量？編輯。謝謝大家給我答案，現在我明白了。

1熱度

2回答

我有一個關於空間（內存）問題的僞代碼的這個特定部分的複雜性： int b(int n, int x) { int sol = x; if (n>1) { for (int i = 1; i <= n; i++) { sol = sol+i; } for (int k=0; k<3; k++) { sol = sol +

-6熱度

1回答

有沒有算法的時間複雜度爲O（sqrt（n）* log（n））？

使用谷歌搜索「有沒有算法的時間複雜度爲O（sqrt（n）* log（n））？」沒有提出任何相關的東西。

1熱度

2回答

如何證明「瓷磚封面」是在NP

嗨即時學習理論計算機科學考試。並且即時學習最近幾年的考試，因爲任務設置每年都非常相似。現在我可以解決幾乎所有這些任務，除了一個：總是有一個關於「p與np」問題的問題。拉特年的一個例子：我們給予「瓦蓋」問題巫婆說：我們有的n×m∈N 的頁長度的「大」矩形，我們有K「小「矩形（」瓷磚「）r1，r2，...，rk 問題是如果所有」小「矩形都適合」大「矩形而不留下任何空間。現在療法是該問題的一些

-2熱度

2回答

是log（n！）= O（（log（n））^ 2）？

我正在練習漸近分析的問題，並且遇到了這個問題。是log(n!) = O((log(n))^2)？我能夠證明 log(n!) = O(n*log(n)) (log 1 + log 2 + .. + log n <= log n + log n + ... + log n) 和 (log(n))^2 = O(n*log(n)) (log n <= n => (log n)^2 <= n*l

0熱度

1回答

時間這雙循環的複雜性

什麼將是這個代碼的時間複雜度？ for(int i = 1 ; i <= b ; ++i) for(int j = i ; j <= b ; j += i)

0熱度

1回答

爲什麼co-P = P

更具體地說，爲什麼有一個TM接受和停止P中的任何補語？據我所知，有一個TM拒絕了來自P的語言L，但爲什麼必須有一個TM接受L的補碼？

0熱度

2回答

設計一個搜索兩個AVL樹之間第k個最大元素的算法

這是上週講座中提出的一個挑戰問題，因爲我一直在思考這個問題。我們被要求創建一個在兩個AVL樹之間搜索第k個最大元素的算法。兩棵樹中的每個節點都包含兩條信息：它的整數值和它在其子樹中包含的子樹的數量（因此樹葉會有1個子樹）。算法的複雜度不能比O（（logn）^ 2）差。我想過將一棵樹中的每個節點與另一棵樹中的每個節點進行比較，但這會是O（n）複雜度太慢。

0熱度

1回答

查找給定代碼的複雜性

我正在努力尋找給定代碼的複雜性。我想我正在努力識別正確的複雜性，以及如何真正分析複雜性。要分析的代碼如下： public void doThings(int[] arr, int start){ boolean found = false; int i = start; while ((found != true) && (i<arr.length)){

2熱度

1回答

嵌套遞歸函數的複雜性分析

我已經寫出了一個小本地計算機代數系統的遞歸算法，其中我將代數運算的操作數列表中的成對還原應用於相鄰操作數列表，因爲代數是非交換）。我想了解我的算法的運行時複雜性（但不幸的是，作爲一名物理學家，自從我選修了處理複雜性分析的本科CS課程以來，這已經很長時間了）。在沒有詳細討論具體問題的情況下，我想我可以用一個功能f來形式化算法，這是一個「分裂」步驟，而函數g組合了結果。然後我的算法將採取以下形式表示：