#algorithm #time-complexity
#алгоритм #временная сложность
Вопрос:
Это похоже на какую-то частичную сортировку.
int n = a.length;
for(int i = 0; i < n; i ) {
while(a[i] != i) {
if(a[i] < 0 || a[i] >= n) //avoid stepping out of range
break;
if(a[i] == a[a[i]]) //avoid inf loop by duplicates
break;
int t = a[i];
a[i] = a[t];
a[t] = t;
}
}
return a;
На первый взгляд кажется, что O (N ^ 2), но когда я запускаю, кажется, что O (N) . Есть идеи? Заранее спасибо.
Комментарии:
1. @Elliott Никакая другая обработка массива не выполняется, например, a = {1, 2, 100, 200}.
2. Внутренний цикл while не зависит от n . Поэтому оно не может быть O (n ^ 2).
3. @lincr, внешний цикл? Число уменьшается как минимум на единицу. Тем не менее, только по этой логике это все еще может быть
O(n^2).
Ответ №1:
Вы правы, что это O(n) :
Чтобы помочь объяснить это, я составлю определение:
Отражающий: элемент a[i] в массиве a является отражающим, если a[i] = i .
Итерации while цикла, которые приводят к break :
Для каждого значения i вы можете иметь ровно одно break значение, которое выполняется в while цикле (включая while условие). Поскольку есть n значения i , это означает, что n общее количество итераций while цикла приводит к break .
Итерации while цикла, которые не приводят к break :
Для этой части может помочь представить наш массив, в котором каждый элемент является либо отражающим ( 1 ), либо неотражающим ( 0 ):
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
Как только мы пройдем break точки, мы узнаем, что a[i] != a[a[i]] (т.е. если мы назовем a[i] as t , то мы это знаем a[t] != t ). И поскольку мы позже присваиваем a[t] = t , то мы изменили элемент массива с неотражающего на отражающий. Обратите внимание, что нигде в вашем коде мы не делаем отражающий элемент неотражающим: присвоение a[i] = a[t] может привести к a[i] неотражению, но мы также знаем, что оно не было отражающим с самого начала, потому while что утверждение было истинным : a[i] != i .
Из нашего визуального представления это означает, что 1 a никогда не изменяется 0 , и все же каждая итерация while цикла (которая передает break точки) приводит по крайней мере к одному 0 переходу к a 1 .
break Как только вы заметите, что каждая (не) итерация внутреннего цикла берет по крайней мере один (возможно, два) неотражающих элемента из массива и преобразует его в постоянно n отражающий, тогда мы понимаем, что общее количество (непрерывных) итераций внутреннего цикла не может превышать для всеговремя выполнения программы.
Вкратце: i повторяется и проверяется во время for цикла n , и каждый выполняет постоянный объем работы, c1 . Существует n общее количество итераций while цикла, соответствующих a break , и не более n итераций, которые не соответствуют a break . Следовательно, всего существует не более 2n итераций while цикла. Работа, выполняемая за одну итерацию while цикла, является некоторой максимальной константой, c2 .
Следовательно, временная сложность <= c1*n c2*2*n = O(n) .
Что касается функции кода, она перестраивает элементы, чтобы сделать как можно больше из них отражающими: если after this функция a[i] неотражающая, то значение i отсутствует в массиве.
Комментарии:
1. Мне нравятся ответы, которые выходят за рамки строки кода или формулы путем объяснения. Приятно. 😉