O(nk)和O(n+k)在时间复杂性上的区别是什么？
[英] what is the difference between O(nk) and O(n+k) in time complexity?
在算法分析中时间复杂性的大o表示法中，当算法取决于n和k时，这两个符号之间有什么区别. 同样，如果有一个嵌套循环运行n次，并且内部循环运行k时间?
In big O notation of time complexity in algorithmic analysis, when an algorithm depends on n and k, what is the difference between these two notations. Also pls help in the notation to use if there is a nested loop with outer loop running n times and inner loop running k times ?
推荐答案
\(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++ )
{}
其他推荐答案
\(O{(n+k)}\) 表示 n 或 k 的较大的线性生长速率.假设 n 更大.然后
n + k <= n + n = 2n = O(n)
如果 n 较小，则
n + k <= k + k = 2k = O(k)
n 是否较大，始终是真的
n + k = O(n+k)
因此，此表示法有助于隐藏这种不确定性.这种两变量的符号对于图形算法很有用，使用 n 对于顶点数量，而边缘数量则有用.您可以编写一个表达式O(n + m)，以指示稀疏图(m = Theta(n))的算法为O(n)，但对于更致密的图(例如，O(n^2)，如果是较慢) m = Theta(n^2)).
对于第二个问题，这只是简单的算术.您在外循环的第一次迭代，第二次的第一次迭代中迭代内部循环k时间，以k+k+k+…+k = n*k总操作，即O(nk).
其他推荐答案
O(nk)表示所花费的时间与n * k成比例. o(n+k)表示所花费的时间与n + k成正比.正是它的样子.您将需要在您不了解的问题的问题中更具体.
在您的情况下，算法的运行时为O(nk)，因为内部循环总共运行n * k times.