具有两个自变量的嵌套 for 循环的时间复杂度

Question

我正在计算这个函数的时间复杂度：

int fun1(A, k){      //A is an array, k is an integer
n = length(A);       //length of array
for j:= 1 to k{
    for i:= j to n{
        if A[i] < A[j-1]{
            x:=  A[j-1]; 
            A[j-1]:= A[i]; 
            A[i]:= x
        }
    }
}
return A[k-1]}

我们在外循环迭代了k次，但是如何计算内循环的迭代次数，以及整个算法的时间复杂度呢？

Answer 1

由于双循环内的功是常数，假设k<=n那么复杂度可以写成

编辑：我忘记了常量，但这没关系，因为它会在大 Oh 符号中消失