java循环的算法时间复杂性
如何找到以下循环的时间复杂性
(一)
int I, j, k, n, mini, tmp;
for(i = 0; i< k; i++){
mini = i;
for(j =i +1; j < n; j++)
if (a[j] < a[mini])
mini = j;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
return a[k-1];
}
2)
void SelectionSort(int A[], int n) {
int i = 0;
while (i < n - 1) {
int j = i + 1;
while (j < n) {
if (A[j] < A[i])
swap(A[j], A[i])
j++;
}
i++;
}
}
# 1 楼答案
两者都是
O(n^2)
1,2在这两种情况下,外部循环从0运行到n(独占),对于每次迭代,内部循环从i+1运行到n(独占)
如果我们对内部循环的运行时间求和,我们得到:
在
O(n^2)
等式(*)来自sum of aritmetic progression
作为旁注——两者都是排序算法,第一个是最小排序,第二个是函数名所说的选择排序
(1)从技术上讲,第一个是
O(k^2)
,但我认为这里的意思是相同的。(2)假设
return a[k-1];
应该在关闭外部循环的作用域之后,并且它的位置是错误的。如果这不是一个错误——外部循环只运行一次,复杂性是O(n)