space-complexity

2熱度

1回答

所以有一個n×n遊戲板，並且棋盤上的每個位置都有一個整數。玩家1從第1行中挑選一個數字，玩家2從第2行挑選一個數字，並且它們交替，直到沒有更多的行。然後他們將所有數字加起來，如果總和等於預定總數S，則玩家1獲勝，否則玩家2獲勝。對於特定的牌局和總和（B，S），玩家1的贏得策略是如果玩家1可以贏得，無論玩家2是什麼。我想證明這個問題是PSpace完成的所以首先我必須證明它在PSpace中，我認爲

3熱度

1回答

什麼時候是Big-Oh（n）= Omega（n）？和theta（n）一樣嗎？

這個問題對我來說很簡單，但只是想看看我是否正朝着正確的方向前進。就像說n = 1時那麼簡單嗎？

17熱度

2回答

後綴數組與後綴樹

我只想知道，當後綴樹優於增強後綴數組。看完Replacing sufﬁx trees with enhanced sufﬁx arrays我沒有看到再使用後綴樹的理由。有些方法可能會變得複雜，但您可以使用後綴數組完成所有工作，可以使用後綴樹執行什麼操作，並且需要相同的時間複雜性，但內存較少。一個survey甚至表明，該後綴陣列的速度更快，因爲它們緩存友好的，並且不產生儘可能多的高速緩存未命中，

3熱度

1回答

打破vs從循環內返回

下面是兩個片段。注意程序之間的唯一區別在於一個break to return和另一個return立即。我知道在一個方法中有一個退出點是很好的設計實踐。但我並不擔心這裏的設計。如果我使用break支付額外費用，我會付多少額外的計算/內存/時鐘週期？計劃之一： public boolean doThis(String[] A){ boolean indicator = false;

-2熱度

2回答

方案中acc函數的時間複雜度？

我一直在試圖找到一個嚴格的限制時間複雜度的這個函數就一個參數。我認爲這是O（p^2）（或者更大的θ），但我不再確定。 (define (acc p n) (define (iter p n result) (if (< p 1) result (iter (/ p 2) (- n 1) (+ result n)))) (iter p n 1))

0熱度

3回答

C＃的空間複雜性排序字符串列表

我正在實現一個程序來排序可能不適合內存的大文件。所有文件將按行排序，所以我想用List來做。我已經計算出內存中有多少行可以分割較小文件中的文件，但是我不知道在內存中需要多少空間來對N個元素列表進行排序。問題是，知道最大數量的元素（已知大小的字符串）和可用內存，List.Sort方法將需要多少內存空間？

3熱度

1回答

Redis數據結構空間需求

redis中排序集和列表之間的空間有什麼區別？我的猜測是有序集是某種平衡的二叉樹，列表是鏈表。這意味着，除了我爲它們中的每一個編碼的三個值之外，關鍵點，分數，值，儘管我會將鏈接列表的分數和值合併在一起，但開銷是鏈接列表需要跟蹤一個其他節點，並且二叉樹需要跟蹤兩個，因此使用有序集合的空間開銷爲O（N）。如果我的值和得分都是長整數，並且指向其他節點的指針也是長整型，那麼單個節點的空間開銷似乎在64位

10熱度

2回答

遞歸算法的空間複雜度

我在採訪時被問到解決檢查pallindrome問題的有效方法。現在我可以做兩兩件事：從i開始= 0到i = N/2和比較第i和n i個字符爲相等。我可以使用遞歸來檢查第一個和最後一個是否相同，而其餘的字符串是pallindrome。第二個是遞歸的。我的問題是算法的遞歸和非遞歸版本的空間複雜度有什麼區別？

2熱度

2回答

術語的含義O（1）空間和不使用額外空間

這對我來說有點混亂。當約束條件如下時，我應該如何解決給定的問題： 1）不使用額外空間：例如：如果我想對給定的數組進行排序，我有幾種方法來完成它。泡沫排序，它繼續交換（只是循環，沒有遞歸）。據我所知，這是沒有使用額外的空間。如果我使用遞歸排序元素，情況如何。它是否與「不使用額外空間」相同，或者使用的堆棧是否計算在算法的空間複雜度中？ 2）在O（1）空間中： O（1）空間的含義是什麼？這是否意味

13熱度

3回答

找到與偶數鑑於陣列出現

的數目，其中每個編號的出現次數是除發生數爲偶數一個數奇數。找到偶數的事件。例如 1, 1, 2, 3, 1, 2, 5, 3, 3 輸出應爲： 2 的下面是約束：號碼不在範圍內。做到位。所需的時間複雜度是O（N）。數組可能包含負數。數組未排序。有了上述限制，我所有的想法都失敗了：基於比較的排序，計數排序，BST，哈希，蠻力。我很想知道：XORing會在這裏工作嗎？如果是，如