通信複雜性

我正在向服務器發送字符串並且想要計算複雜性。通信複雜性

對於每個字符串s我發送s的所有預製件。因此，我先發送一個字符，然後是兩個字符，然後是三個字符，直到發送|s|個字符。

這裏的通信複雜性是什麼？我會說O(|s|²)，但我不確定。

另外在另一種算法中，我發送的每個字符s的固定大小的數據量，比方說100個字符。所以我發送|s| * 100個字符。現在這個應該在O(|s|)對不對？但哪一個更糟？很明顯簡短s第一個算法是更好的，或者我完全在這裏？

來源

2014-10-20 Blub

請糾正我，如果我錯了。

發送一個字符，然後兩個字符，然後三個...直到發送| s |字符。

當您發送第一個字符時，是剩餘字符（| S | -1）還是每次都要重新開始| S |

對於第一種可能性：

假設| S | = N

1 + 2 + ... + N = N（N-1）/ 2

在這種情況下的複雜度爲：O（| S |^2）

對於第二個可能性： 1 + 2 + ... +α= | S |

在這種情況下複雜度爲：O（| S |）

線性時間複雜度是所有的時間更好，檢查本教程中，瞭解更多有關complexity time

來源

2014-10-20 02:15:49 user3378649

是的，這是第一個。但我想知道，假設我知道| s |總是小於100（線性時間複雜度爲100），那麼'| s |^2'複雜度就不會更高效了。 – Blub 2014-10-20 03:08:47

「高效」是非常主觀的。如果你有兩個解決方案，你想比較，你可以根據大O的複雜性來決定哪一個更有效。但在這種情況下，我看不到你有兩種方法。如果s小於100，那麼這不是問題（如果你知道排序算法，一些研究人員更喜歡使用插入排序，儘管事實是二次的，當它們的元素尺寸小於100時）。 – user3378649 2014-10-20 03:12:45

令C代表的因素在第二個算法中。在你的例子中，你設置c爲100.然後你的第二個算法將需要c * | s |要傳送的字符。正如user3378649指出的那樣，您的第一個算法需要傳遞| s | *（| s | -1）/ 2個字符。

因此，現在應該很容易看出，只要c * | s | = | S | *（| S | -1）/ 2，或更簡潔地：

C =（| S | -1）/ 2

顯然，如果c <（| S | -1）/2那麼第二個算法的代價就會更小，如果c>（| s | -1）/ 2，那麼第一個算法的代價就會更小。

說了這麼多，你應該考慮這些想法作爲一個實際問題：

什麼是典型的價值| S |？如果您有保證其中一個不平等總是被滿足（例如，如果您可以保證| s | < 10），您應該選擇適當的算法。
怎麼會容忍你的系統是更長的延遲？如果你一直使用第一種算法，當你得到一個非常大的字符串時，你可能會遇到麻煩。即使99％的數據真的很短，由長時間延遲引起的潛在用戶影響也可能成爲問題。
您可以考慮使用都算法：採用第一種算法，當| S |很小，在| s |時使用第二種算法很大。
你有沒有考慮剛剛發送的合理大小的區塊整個字符串，並讓通信人物的另一面出來的前綴？數據傳輸通常比計算時間更昂貴。此外，必須考慮啓動通信的成本。通信傳輸通常使用塊大小的最小值，所以應該阻止分解小信息。

祝你好運！

來源

2014-10-20 16:51:13

回答

相關問題