通信复杂性
问题描述：
我正在向服务器发送字符串并且想要计算复杂性。通信复杂性
对于每个字符串s我发送s的所有预制件。因此，我先发送一个字符，然后是两个字符，然后是三个字符，直到发送|s|个字符。
这里的通信复杂性是什么？我会说O(|s|²)，但我不确定。
另外在另一种算法中，我发送的每个字符s的固定大小的数据量，比方说100个字符。所以我发送|s| * 100个字符。现在这个应该在O(|s|)对不对？但哪一个更糟？很明显简短s第一个算法是更好的，或者我完全在这里？
答
请纠正我，如果我错了。
发送一个字符，然后两个字符，然后三个...直到 发送| s |字符。
当您发送第一个字符时，是剩余字符（| S | -1）还是每次都要重新开始| S |
- 对于第一种可能性：
假设| S | = N
1 + 2 + ... + N = N（N-1）/ 2
在这种情况下的复杂度为：O（| S |^2）
- 对于第二个可能性： 1 + 2 + ... +α= | S |
在这种情况下复杂度为：O（| S |）
线性时间复杂度是所有的时间更好，检查本教程中，了解更多有关complexity time
答
令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 |时使用第二种算法很大。
- 你有没有考虑刚刚发送的合理大小的区块整个字符串，并让通信人物的另一面出来的前缀？数据传输通常比计算时间更昂贵。此外，必须考虑启动通信的成本。通信传输通常使用块大小的最小值，所以应该阻止分解小信息。
祝你好运！
是的，这是第一个。但我想知道，假设我知道| s |总是小于100（线性时间复杂度为100），那么'| s |^2'复杂度就不会更高效了。 – Blub 2014-10-20 03:08:47
“高效”是非常主观的。如果你有两个解决方案，你想比较，你可以根据大O的复杂性来决定哪一个更有效。但在这种情况下，我看不到你有两种方法。如果s小于100，那么这不是问题（如果你知道排序算法，一些研究人员更喜欢使用插入排序，尽管事实是二次的，当它们的元素尺寸小于100时）。 – user3378649 2014-10-20 03:12:45