O(nk)和O(n + k)在时间复杂度上有什么区别？

Question

在算法分析中时间复杂度的大O表示法中,当算法依赖于n和k时,这两个符号之间的区别是什么.如果有一个嵌套循环,外循环运行n次,内循环运行k次,请帮助使用符号？

Answer 1

O(NK):

for( i=0; i<n; i++ ) {
   for( j=0; j<k; j++ )
   {}
}

O(N + K):

for( i=0; i<n; i++ )
{}

for( j=0; j<k; j++ )
{}

Answer 2

O(nk) 表示所花费的时间与 成正比n * k。O(n+k) 表示所花费的时间与 成正比n + k。事实确实如此。您需要更具体地提出您不明白的问题。

在您的例子中，算法的运行时间是 O(nk)，因为内部循环总共运行了多次n * k。