asymptotic-complexity

1熱度

1回答

我目前正在通過MIT 6.006課程的在線課程材料獲得樂趣。我在問題集＃2（找到了here），並對koch雪花問題（問題＃1）漸近渲染時間的計算有疑問。根據這些解決方案，當CPU負責渲染和座標計算時，漸進渲染時間比CPU和GPU之間的分離過程更快。數學對我來說是有道理的，但是有沒有人對此有直覺？在我看來，CPU仍然需要計算渲染雪花（Theta（4^n）時間）的座標，然後必須渲染圖像。在我看來，

0熱度

2回答

確定大哦符號

在我籌備算法考試我試圖解決以下幾個大哦問題，所以你可以檢查他們對我 for(i=1; i<n; i++){ i=i*3; for(j=15; j>=6; j--){ System.out.print(i*j); } } 答：O（LG ñ ） for(j=1; j<n; j++){ System.out.print(j*2); } for(k=n;k>=1; k=k/2)

0熱度

1回答

計算log（n）+Ө（sqrt（n））的漸近極限

假設f(n) = Ө(sqrt(n))。通過大-θӨ的定義，我們可以說：存在兩個常量c1和c2，既有真正的正數，使得：c1*sqrt(n) <= f(n) <= c2*sqrt(n) 所以，我們有以下的總和：log(n) + f(n)。我在想寫log(n)爲Ө(log(n))。因此，總和將Ө(sqrt(n))考慮Ө(sqrt(n))大於Ө(log(n))，但我還是不明白我怎麼能在這裏計算漸

-3熱度

2回答

證明5^n = o（n！）

請幫我提供一個方向來說明如何證明這一點。我可以通過隨機發現n的值來證明n！大於5^n。但有人可以幫助我用數學證明。

-1熱度

1回答

無法理解算法中的執行時間

我很難確定算法中每個步驟的執行時間。我無法理解這個邏輯。我們都知道在算法中確定Big O或Theta之前，我們必須計算每一步的執行時間，然後根據執行時間來計算順序。我覺得比大O或theta計算順序更容易，但我的問題是計算執行時間。實施例： for i=0 to **n** dothisStep 的這個執行時間是：（N + 1），這使得它的O（N）的命令 - 這是一個容易和我理解why-

0熱度

1回答

算法與O（N /日誌（n））的複雜性

是否有這種複雜的算法出名？（1，log（n））中隨機生成的數字（具有均勻分佈），我想也許是一個跳過列表，其中節點的級別不是由尾數投幣次數決定的，而是使用從期間來確定節點的級別。這樣的數據結構將具有find（x）操作的複雜度爲O（n/log（n））（我認爲至少）。我很好奇是否還有別的東西。

0熱度

1回答

漸近分析不等式

對於這個漸近分析問題，我有一個理解如何導出以紅色突出顯示的不等式的問題。有人能解釋這些不平等的性質以及它們是如何形成的。下面的圖片有問題和解決方案。以紅色突出顯示的部分是我無法理解的地方。圖片的問題和解決方案的

1熱度

1回答

嵌套循環運行時間？

正在運行什麼時間好大哦批註： for(int i=1;i<N;i++) for(int j=1;j<N;j*=2) 循環將停止，當j> N，如果我們讓k爲循環的一些任意迭代，J對迭代k值將是2K 。當k> log2 n時發生2k> n，循環停止。因此，迭代的次數只有O（log n），所以總的複雜度是O（log n）。這是正確的嗎？

1熱度

1回答

最大大小總和爲n

現在的問題是從本地黑客馬拉松：我有一個正序整數排序降序排列。例如（9,4,2,1）。您可以遍歷數組中的n個元素以最大化總和（最初n =數組的大小）。當你從頭到尾遍歷數組時，你可以隨時停下來再從頭開始，但是這樣做的代價是你從你的津貼中失去了一個元素。例如，在這種情況下，最好的方法是9,0,9,4。請注意，我已經停止了，失去了一個元素（因此爲0）並繼續。我想用動態規劃解決這個問題。我知道如何在O（

0熱度

1回答

我怎樣才能使O（N）而不是O（N^2）的性能？

我想了解如何使這個問題的時間複雜度更好：非空零索引數組一個由N個整數給出。陣列A的連續元素代表道路上的連續車輛。數組A僅包含0和/或1：0代表向東行駛的汽車，1代表向西行駛的汽車。目標是計數過往車輛。我們說一輛汽車（P，Q）其中0≤P< Q < N在P向東行駛並且Q 向西行駛時通過。例如，考慮數組A，使得： A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1