c++ - O(2m+n) 和 O(kn) 的时间复杂度

Question

例如假设有一个函数迭代大小为 m 的数组两次和大小为 n 的数组一次

func(){
   for(i = 0; i < m; i++){//do something}
   for(i = 0; i < n; i++){//do something}
   for(i = 0; i < m; i++){//do something}
}

将其时间复杂度写为 O(2m+n) = O(m+n) 是否正确，因为 O(2m) = O(m)？

对于另一个问题，如果我有一个函数迭代大小为 n 的数组，k 次，其中 k 是在调用函数之前根据输入计算的。

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

是否可以说它的时间复杂度是 O(k*n) = O(n)，原因与第一个问题相同？

Answer 1

Is it correct to write its time complexity as O(2m+n) = O(m+n), since O(2m) = O(m)?

是的。大 O 表达式的项可以分成单独的大 O 表达式，所以 O(2m+n) = O(2m) + O(n) = O(m) + O(n) = O( m+n)

Is it ok to say that its time complexity is O(k*n) = O(n) for the same reason as in the first question?

不，因为k 不是常量。