Ако виждаш това съобщение, значи уебсайтът ни има проблем със зареждането на външни ресурси.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Основно съдържание

Анализ на сортиране чрез пряка селекция

Сортирането чрез пряка селекция обхожда индексите на масива; за всеки индекс сортирането извиква функциите indexOfMinimum и swap. Ако дължината на масива е n, в масива има n индекса.
Тъй като при всяко изпълнение на цикъла се изпълняват два реда код, може да си помислиш, че сортирането чрез пряка селекция изпълнява 2n реда код. Това обаче не е вярно! Запомни, че indexOfMinimum и swap са функции: когато някоя от тях се извика, се изпълняват някакви редове код.
Колко реда код се изпълняват при едно извикване на swap? При обикновената имплементация има 3 реда и затова всяко извикване на swap отнема константно време.
Колко реда код се изпълняват от едно извикване на indexOfMinimum? Трябва да вземем предвид цикъла в indexOfMinimum. Колко пъти се изпълнява този цикъл при едно извикване на indexOfMinimum? Зависи от размера на подмасива, който обхожда. Ако подмасивът е целият масив (както е в първата стъпка), цикълът се изпълнява n пъти. Ако размерът на подмасива е 6, цикълът се изпълнява 6 пъти.
Да кажем, че целият масив има размер 8 и да помислим как работи сортирането чрез пряка селекция.
  1. При първото извикване на indexOfMinimum трябва да обходи всяка стойност от масива и затова цикълът в indexOfMinimum се изпълнява 8 пъти.
  2. При второто извикване на indexOfMinimum, трябва да обходи всяка стойност в подмасива с индекси от 1 до 7 и така цикълът в indexOfMinimum се изпълнява 7 пъти.
  3. При третото извикване обхожда подмасива от индекс 2 до индекс 7; тялото на цикъла се изпълнява 6 пъти.
  4. При четвъртото извикване се обхожда подмасива с индекси от 3 до 7; цикълът се изпълнява 5 пъти.
  5. При осмото и последно извикване на indexOfMimimum, тялото на цикъла се изпълнява само веднъж.
Ако съберем броя на изпълненията на тялото на цикъла в indexOfMinimum, получаваме 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 пъти.

Странична бележка: Изчисляване на сумата от 1 до n

Как да изчислим бързо сумата 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1? Ето ви един трик. Да съберем числата в интересен ред. Първо да съберем 8 + 1, най-голямата и най-малката стойност. Получаваме 9. След това да съберем 7 + 2, втората най-голяма и втората най-малка стойност. Интересно, но отново получаваме 9. Ами 6 + 3? Отново 9. Накрая 5 + 4. Отново 9! Какво получаваме?
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=49=36 .
Има четири двойки числа, всяка от които се сумира до 9. Ето ти трик, с който да сумираш всяка поредица от последователни цели числа:
  1. Събираме най-малкото и най-голямото число.
  2. Умножаваме по броя на двойките.
Ами ако числата в поредицата са нечетен брой и не можеш да ги събереш по двойки? Няма значение! Просто преброй единственото число в средата на поредицата като половин двойка. Например да сумираме 1 + 2 + 3 + 4 + 5. Имаме две двойки (1 + 5 и 2 + 4, всяка от които се сумира до 6) и една половин двойка (3, което е половината от 6), и получаваме общо 2,5 двойки. Умножаваме 2,56=15 и получаваме верен отговор.
Ами ако поредицата продължава от 1 до n? Наричаме това аритметична прогресия. Сумата на най-малкото и на най-голямото число е n+1. Тъй като има общо n числа, има n/2 двойки (без значение дали n е четно или нечетно). Следователно сумата от числата от 1 до n е (n+1)(n/2), което е равно на n2/2+n/2. Опитай тази формула за n=5 и n=8.

Асимптотичен анализ на времето за изпълнение на сортирането чрез пряка селекция

Общото време за изпълнение на сортирането чрез пряка селекция има три части:
  1. Времето за изпълнение на всички извиквания на indexOfMinimum.
  2. Времето за изпълнение на всички извиквания на swap.
  3. Времето за изпълнение на останалата част от цикъла във функцията selectionSort.
Част 2 и част 3 са лесни. Знаем, че извикванията на swap са n на брой, а всяко извикване отнема константно време. Като използваме нашата асимптотична нотация, времето за всички извиквания на swap е Θ(n). Останалата част от цикъла в selectionSort е просто тестване и увеличаване на променливата брояч и извикване на indexOfMinimum и swap и по този начин отнема константно време за всяка от итерациите, които са n на брой, за време Θ(n).
Вече свършихме трудната част за времето за изпълнение на всички извиквания на indexOfMinimum в част 1. Всяка отделна итерация на цикъла в indexOfMinimum отнема константно време. Броят итерации в този цикъл е n при първото извикване, след това n1, после n2 и т.н. Вече видяхме, че тази сума 1+2++(n1)+n е аритметична прогресия и се изчислява до (n+1)(n/2) или n2/2+n/2. Следователно общото време за всички извиквания на indexOfMinimum е някакво константно време n2/2+n/2. В контекста на нотацията big-Θ не се интересуваме от тези константни множители, нито от множителя 1/2, нито от членовете от нисък порядък. В резултат времето за изпълнение за всички извиквания на indexOfMinimum е Θ(n2).
Събираме времената за изпълнение на трите части и получаваме Θ(n2) за всички извиквания на indexOfMinimum, Θ(n) за извикванията на swap и Θ(n) за останалата част от цикъла в selectionSort. Членът Θ(n2) е най-важен и затова казваме, че времето за изпълнение на сортирането чрез пряка селекция е Θ(n2).
Забележи, че никой от случаите не е отчасти добър или отчасти лош за сортирането чрез пряка селекция. Цикълът в indexOfMinimum винаги ще отнеме n2+n/2 итерации без значение от входните данни. Следователно можем да кажем, че сортирането чрез пряка селекция се изпълнява за време Θ(n2) във всички случаи.
Да видим как времето за изпълнение Θ(n2) влияе върху действителното време за изпълнение. Да кажем, че сортирането чрез пряка селекция отнема около n2/106 секунди за сортиране на n стойности. Да започнем с малка стойност на n, да речем n=100. Тогава времето за изпълнение на сортирането чрез пряка селекция е около 1002/106=1/100 секунди. Това изглежда доста бързо. Ами ако n=1000? Тогава сортирането чрез пряка селекция отнема около 10002/106=1 секунди. Размерът на масива е 10 пъти по-голям, но времето за изпълнение се увеличи 100 пъти. Ами ако n=1,000,000? Тогава сортирането чрез пряка селекция отнема 1,000,0002/106=1,000,000 секунди, което е малко повече от 11,5 дни. Увеличаването на размера на масива 1000 пъти увеличава времето за изпълнение милион пъти!
Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Все още няма публикации.
Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.