当给定一个实际运行时，如何计算运行时复杂性(`‘O(M)’)？
当给定一个实际运行时，如何计算运行时复杂性(`‘O(M)’)？
提问于 2013-11-14 16:36:06
我试着简短地问一问：
我有一个算法，作为一个函数，让我们称之为f
void f(int[1..N]) {
// algorithm goes here
}现在，我有了用于real runtime输入的N。
请假定函数time()以毫秒为单位返回当前系统的时间。
int[1...N] n;
unsigned long start = time(), end;
f(N);
end = time();
printf("Real runtime: %ul", end - start);换句话说，我知道f将为参数N运行多少毫秒。
根据这些信息，如何计算f(N)运行时复杂性，即f = O(N)
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-11-14 16:44:33
对于不同的N，您需要几个数据点。
假设你得到了这些统计数据：
N time(ms)
4 12
8 24
16 48在这种情况下，加倍N是时间的两倍，所以您的复杂度必须是O(N)。
但如果你得到这些数据
N time(ms)
4 16
8 64
16 256在这种情况下，加倍n是运行时的四倍，所以复杂性必须是O(n2)。
如果时间没有变化，你的复杂度是O(1)。
类似地，不同的数据点将允许您确定满足大(O)的函数。对于不同的N，你拥有的点数越多，你就能越好地确定这个函数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19983178
复制相关文章
相似问题
腾讯云开发者
