Avantika P Ответов: 3

Сколько раз выполняется цикл while, в худшем случае сложности?


Считая каждую операцию как 1 операцию (включая []), сколько раз цикл while выполняется в этом коде?

int i, float x;
for(int j=1; j<n; j++)
{
 x=v[j];
 i=j-1;
  while(v[i] > x && i>=0) /** in context with this while loop **/ 
  {
     v[i+1]= v[i];
     i= i-1;
  }
  v[i+1]= x;
}


Что я уже пробовал:

подсчитано количество операций цикла while для каждой итерации цикла for. Хотел перепроверить.

Maciej Los

В чем проблема, чтобы проверить это по коду?

3 Ответов

Рейтинг:
2

Patrice T

Это выглядит как неэффективный способ перевернуть список.
Цикл while должен выполняться примерно (n2-n)/2 раза.


Рейтинг:
0

OriginalGriff

Это разновидность пузырькового типа: так что посмотрите на большую нотацию O для этого, и вы должны быть в состоянии решить ее.
Сортировка пузырьков | блестящая математика и наука Wiki[^]


Рейтинг:
0

PrafullaVedante

Два вложенных цикла, каждый с максимальным числом итераций n.
Общая временная сложность = n x n = n^2