Calculating Big O

Question

Я новичок в программировании, и я пытаюсь выяснить, как вычислить алгоритмы Big O алгоритмов. Например:

int selectkth(int a[], int k, int n){ 
    int i, j, mini, temp; 
    for(i=0, i < k, i++){ 
     mini = i; 
     for(j = i+1; j < n; j++) 
     if(a[j] < a[mini]) 
     mini = j; 
     temp = a[i]; 
     a[i] = a[mini]; 
     a[mini] = temp; 
     } 
     return a[k-1]; 
    } 

Я знаю, что есть 9 шагов, происходящие здесь, и что вложенные циклы, как предполагается, должны быть умножены вместе. Я получил O (n^2), когда я впервые попытался, но я не думаю, что это правильно. Может кто-нибудь объяснить, как правильно рассчитать Big O упрощенным способом для новичков, подобных мне? Любое объяснение поможет или ваши собственные примеры. Спасибо :)

Answer 1

o (n^2) является правильным. Самый большой фактор времени выполнения вашего кода - это два вложенных цикла. другой материал просто обрабатывает переменные, о которых вам не нужно беспокоиться. Большой O здесь на самом деле k n = n n = n * 2 = O (n^2) Это длина массивов. k раз n.

Answer 2

For outer loop, there k iteration 
for inner loop: 
For iteration #1 : n times array manipulation 
For iteration #2 : n - 1 times array manipulation 
. 
. 
For iteration #k : n - k times array manipulation 

total array manipulation = n + (n-1) + ..... + (n -k) 
= n(n+1)/2 - k(k+1) /2 
=~(n*2 - k*2) 

= ~(n*2) // if n is very very greater than k