下面函数的Big Oh表示法中最坏的运行时间是多少？有人能解释一下原因吗？谢谢
test{
int counter = 0;
for int(i=0; i<5000;++i){
counter += i;
for(j=0;j<n;++j){
...
}
for(k=0;k<i;++k){
...
}
}
}
5000是一个常数，所以它并不重要。唯一重要的是有n的for循环，所以这是O(n(。
Big-O表示法告诉您算法缩放与函数相同或比函数慢。
-
O(N(意味着，如果您的输入数据增加了10倍，则所需时间将增加或减少10倍。
-
O(N^2(意味着在10倍以上的数据下，它的长度是100倍或更短。
您的输入是n，i在一个共循环上。因此，你的复杂性是O(n(，因为n在for循环中，所以它是线性缩放的，除非你在另一个循环中使用n。
你可能已经注意到"；或更小"；，你可能会争辩说，所有的O(N(算法因此也是O(N^2(或更糟，这在技术上是正确的，但没有帮助。这就是为什么你会选择最快的Big-O表示法来表示一个好的近似值。
Big-O表示法谈论运行时间与n成比例。这里，除了一个内部有n的循环外，所有循环都重复相同的次数。因此，当n改变时，只有内部循环的运行时间改变，所以它是O(n(。