0

我有一个方法,我想计算它的运行时间:

print()
{
node* p1 = sentinel_->next_;
while(p1 != sentinel_)
cout << p1->data_ << “ “;
p1 = p1->next_;
}
cout << endl;
}

如果我假设while循环可以执行n-1次。所以: T(n) = 1 + (n-1) + (n-1) + (n-1) + 1 = 3n - 1。 但是对于“输入大小”N,使用的正确值是多少?它是否会基于T(n) , 它是3n - 1 >= 0 所以 n >= 1/3 或者n只是大于或等于1,因为 while 循环至少可以执行一次。

4

1 回答 1

0

算法复杂度通常用渐近符号计算。这意味着算法如何随着输入大小的变化而变化。

对于您的示例,“n”可以是任何东西。如果 n == 2,则您的 while 循环将运行一次,如果 n == 3,则您的 while 循环将运行两次...通常,正如您提到的,while 循环对于给定的值运行“n-1”次“n”。这意味着随着“n”值的增加,您的 while 循环将需要更长的时间来运行。因此,算法的复杂性直接取决于循环运行的次数。并且循环运行的次数由“n”的值决定。因此,您的代码的运行复杂度为 O(n)。

假设您有一个方法,您首先遍历列表并将每个节点值加 10。然后,您再次遍历列表以打印每个节点值。该算法的运行复杂度为 O(n) + O(n) = 2 * O(n)。这仍然等同于 O(n) 运行时间,因为常量被忽略了。同样,这只是理论上的。实际上,您在列表上循环了两次,这会使程序变慢。

我希望我的解释清楚。我没有使用任何技术术语,但我希望你明白这一点。

于 2013-10-06T21:52:03.453 回答