Лучшая производительность и наихудшая производительность в алгоритме

Question

Я немного смущен по этой теме.

Если список уже отсортирован, мы скажем, что наилучшая производительность - n.

и для некоторого алгоритма, такого как сортировка пузыря, мы говорим, что худший случай - это n^2.

Мое замешательство, почему мы говорим его n^2 ?? как появилась эта площадь? каково предположение, которое мы делаем, чтобы сохранить квадрат? Почему мы не даем его, как O (1), O (log n), O (n), O (2^n)? пожалуйста, помогите мне понять эти термины ... статьи, блог, лекционные заметки .. любая помощь.

Я новичок.

Answer 1

Чтобы понять сортировку пузырьков (или любой вид, действительно), вам нужно продумать процесс, который он использует. Например, сортировка пузырьков работает, просматривая весь список, заменяя нелегальные пары. В худшем случае он делает n - 1 свопов на первом проходе, исследуя все n элементов. Для второго прохода гарантируется, что последний элемент в порядке - так как он будет «барботирован» до конца. Таким образом, сортировка должна составлять не более n-2 свопов, исследуя n-1 элементов и т. Д. Следовательно, наихудший сценарий O (n^2).

Если вы можете понять , как работает, то вы можете рассчитать наилучшие и наихудшие сценарии. Вы можете начать в Википедии:

http://en.wikipedia.org/wiki/Sorting_algorithm

P.S. - Сорт пузыря в значительной степени самый худший сорт. Однако, если вы сортируете отсортированные данные, он работает лучше других.

Answer 2

O (n^2) подразумевает, что алгоритм (сортировка пузырьков) в худшем случае должен выполнять n^2 сравнения (больше, меньше, равно), где n - количество элементов сортируются.

Answer 3

Я думаю, что это то, что вы ищете.

http://en.wikipedia.org/wiki/Best,_worst_and_average_case

Answer 4

Предположим, что мы имеем следующие простые программы, и мы хотим, чтобы найти свою временную сложность.

return_sum(n) 
{ 
y=4 

while(n>0) 
{ 
y=y+y 
n=n-1 
} 
return y 
} 

Компьютерная программа состоит из нескольких этапов, временную сложность программы можно рассматривать как количество шагов, которые программа предпринимает для решения конкретной проблемы.

Количество шагов, необходимых return_sum() программа:

return_sum(n) 
{ 
y=4  // this step will take constant time say, c1, and will run only once 

while(n>0) //this step run n time , if step takes c2 time , total time is n * c2 
{ 
y=y+y  // this step will run n-1 time , total time (n-1) * c3 
n=n-1 // this step will run n-1 time , total time (n-1) * c4 
}return y // takes constant time c5, run once. 
} 

Позволяет добавить время, затрачиваемое на все операции, чтобы выполнить эту программу

= c1 + n * c2 + (n-1) * c3 + (n-1) * c4 +c5 
    = n(c2 + c3 + c4) + (c1+ c5 - c2 - c3) 

Где (c2 + c3 + c4) и (c1 + c5 - c2 - c3) постоянны, мы можем обозначить их как a и b.

=an + b 

Это функция от п,

F (п) = ап + B

И эта функция О (п). Таким образом, временная сложность этой программы O (n).

Доказательство:

f(n) = an+b 

Lets give a and b any constant values , suppose a = 100 and b = 200 

Now for all sufficient large value of n >=1. 
             100n < 200n 
and          
             200 < 200n 

        f(n)=100n+200 < 200n + 200n 
            < 400n     
            < 400 * n    where c = 400 and n0 = 1 
           f(n)= O(n) 

Аналогично, если мы добавим все шаги вставки рода мы получаем F '(п), что

     f'(n) = an^2+bn+c 

По доказанному мы можем легко найти, что f '(n) = O (n^2)

Answer 5

Ну много ответов много текста (некоторые из них большие)
, но не один достаточно просто один для тупого
так я попробовать:

в: 0,3,7,8 ... не п = 4 лучшем случае
1. 0,3, 7,8
2. 0, 3,7, 8
3. 0,3, 7,8
- никаких изменений поэтому его сортировка ... O (n-1) -> ~ O (n)

в: 8,7,3,0 ... п = 4 наихудший сценарий
1. 7,8, 3,0
2. 7, 3,8, 0
3. 7,3, 0,8
- изменение произошло, так что не остановить пока
4. 3,7, 0,8
5. 3, 0,7, 8
6 3,0, 7,8
- изменение произошло, так что не остановить еще
7. 0,3, 7,8
8. 0, 3,7, 8
9. 0,3, 7,8
- нет изменений происходят так его отсортирован ... O ((п-1)^2) -> ~ O (N^2)

Надеется, что я не сделал глупую ошибку где-то .. и это помогает кому-то говорить.