Най-добър, среден и най-лош случай

Код на:JavaC#PythonJavaScript

Накратко: Най-лошият случай е най-многото работа, която алгоритъмът прави при вход с размер n; него обещаваме, а средният случай е очакваната работа при предположение за входа, обикновено че всеки вход е еднакво вероятен.

Проблем

При теста е мигновено

Поддръжката на магазина търси поръчка по номер, когато клиент се обади. Поръчките на месеца са в списък, по реда на поръчване. Колегата, който написа търсенето, го пробва с поръчка 1001 и казва: „Една проверка. Мигновено е, колкото и поръчки да има.“

Месец по-късно поддръжката се оплаква: понякога търсенето е бързо, понякога се бави. Най-много се бави, когато клиентът сбърка номера и такава поръчка няма.

И двете са верни. Едно и също търсене прави една проверка или прави всичките. Колко е бързо тогава? Кое число да кажеш на поддръжката?

Идеята

Три случая на един алгоритъм

Броят операции зависи не само от n, а и от това какъв е входът. Затова се гледат три случая:

• най-добрият: входът, при който работата е най-малко. Тук търсената поръчка е първата;
• най-лошият: входът, при който работата е най-много. Тук поръчката е последна или я няма;
• средният: колко е работата средно, ако входовете идват по някакво правило, обикновено „всеки е еднакво вероятен“.

Колегата е мерил най-добрия случай и е казал O(1). Но линейното търсене е O(n): при n поръчки проверките може да са n.

Виж го

Търсенето с брояч

Търсенето проверява поръчките една по една и спира, когато намери номера:

checks = 0


def find_order(ids, wanted):
    global checks
    for i in range(len(ids)):
        checks += 1
        if ids[i] == wanted:
            return i
    return -1

report нулира брояча, търси и печата мястото (-1, ако поръчката я няма) и проверките:

def report(ids, wanted):
    global checks
    checks = 0
    at = find_order(ids, wanted)
    print(f"{wanted}: {at}, проверки: {checks}")

Три търсения в 1 000 поръчки: първата, тази в средата и номер, който го няма:

ids = [1001 + k for k in range(1000)]
report(ids, 1001)
report(ids, 1501)
report(ids, 999)

Изход

1001: 0, проверки: 1
1501: 500, проверки: 501
999: -1, проверки: 1000

Виж го

Едно търсене, три случая

checks = 0


def find_order(ids, wanted):
    global checks
    for i in range(len(ids)):
        checks += 1
        if ids[i] == wanted:
            return i
    return -1


def report(ids, wanted):
    global checks
    checks = 0
    at = find_order(ids, wanted)
    print(f"{wanted}: {at}, проверки: {checks}")


ids = [1001 + k for k in range(8)]
report(ids, 1001)
report(ids, 1005)
report(ids, 999)

Стъпка по стъпка, с думи

1. 8 поръчки от месеца, с номера от 1001 до 1008 по реда на поръчване. Търсенето върви от началото, една по една.
2. Най-добрият случай: поръчката е първата. 1 проверка и търсенето свършва. Изход: 1001: 0, проверки: 1.
3. Поръчката е в средата: 5 проверки, n/2 + 1. Изход: 1005: 4, проверки: 5.
4. Най-лошият случай: такава поръчка няма. Търсенето проверява всичките 8 и чак тогава връща -1. Изход: 999: -1, проверки: 8.
5. Средният случай: ако всяка поръчка се търси еднакво често, проверките са 1, 2, …, 8. Средно (1 + … + 8) / 8 = 4,5: около n/2. Пак O(n).
6. Обещава се най-лошият случай: най-много n проверки, каквото и да търсят. Линейното търсене е O(n).

Едни и същи 8 поръчки, едно и също търсене. Разликата е само в това какво се търси.

Идеята

Защо се обещава най-лошият

Най-добрият случай не казва нищо. Почти всеки алгоритъм е бърз, ако входът е подходящ. Да обещаеш най-добрия значи да разчиташ на късмет.

Най-лошият е обещание. „Най-много n проверки, каквото и да търсят.“ С това число планираш: колко поръчки може да търси поддръжката, преди страницата да стане бавна. Затова, когато кажат „линейното търсене е O(n)“, имат предвид най-лошия случай.

Средният е полезен, но иска предположение. Ако всяка поръчка се търси еднакво често (случаен вход), търсенето на всяка по веднъж дава средното:

ids = [1001 + k for k in range(1000)]
total = 0
for wanted in ids:
    checks = 0
    find_order(ids, wanted)
    total += checks
print("Общо: " + str(total))
print("Средно: " + str(total / len(ids)))

Изход

Общо: 500500
Средно: 500.5

(1 + 2 + … + 1 000) / 1 000 = 500,5: около n/2. Константата ½ не сменя класа: средният случай също е O(n). Но ако търсят предимно нови поръчки, или предимно сбъркани номера, средното е друго. Предположението за входа е част от отговора.

Пусни трите случая на Bench:

• Търсената поръчка е първа O(1)
• Търсената поръчка е в средата O(n)
• Такава поръчка няма O(n)

Алгоритъм	n = 10	n = 1000	n = 100 000
Търсената поръчка е първа	1	1	1
Търсената поръчка е в средата	6	501	50 001
Такава поръчка няма	10	1000	100 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

По-точно, за любопитните

Вграденото търсене в списък е същото линейно търсене. ids.index(wanted) и wanted in ids минават елементите един по един: O(n) в най-лошия случай. За разлика от другите езици, index не връща -1, а хвърля ValueError, ако елементът го няма.

Кога средният и най-лошият случай са много различни. Има алгоритми, които са бързи почти винаги, а на редки входове стават много по-бавни. Quick sort е средно O(n log n), а с лош избор на делителя става O(n²) (ще го видиш в урока за quick sort). Hash таблицата намира средно с една стъпка, а ако всички ключове паднат в една кофа, с n (модулът „Структури от данни“). Там се казват и двата случая, защото и двата имат значение.

Пробвай

Предвиди изхода

Шест поръчки, три търсения. Колко проверки печата програмата?

ids = [1001, 1002, 1003, 1004, 1005, 1006]
for wanted in [1004, 1006, 1010]:
    checks = 0
    find_order(ids, wanted)
    print(checks)

Отговор

3 / 5 / 6

4 / 6 / 0

4 / 6 / 6

Провери

Пробвай

Намери грешката

Някой пише търсенето така:

def find_order(ids, wanted):
    global checks
    found = -1
    for i in range(len(ids)):
        checks += 1
        if ids[i] == wanted:
            found = i
    return found

ids = [1001 + k for k in range(8)]
report(ids, 1001)
report(ids, 1005)
report(ids, 999)

Изход

1001: 0, проверки: 8
1005: 4, проверки: 8
999: -1, проверки: 8

Намира вярното място, но всяко търсене прави по 8 проверки. На кой ред е грешката?

Избери реда с грешката.

1def find_order(ids, wanted):2 global checks3 found = -14 for i in range(len(ids)):5 checks += 16 if ids[i] == wanted:7 found = i8 return found

Провери

Упражнение

Новите поръчки се търсят най-често

Реши задачата в редактора си.

Търсене от края. Поддръжката почти винаги търси поръчки от последните дни. Напиши find_latest, което търси от края към началото и брои проверките, и го пусни в report за 1 000 поръчки с номерата 2000 (последната), 1001 (първата) и 999 (няма я):

Изход

2000: 999, проверки: 1
1001: 0, проверки: 1000
999: -1, проверки: 1000

Кой е най-добрият случай сега? А най-лошият? Сменил ли се е класът?

Още задачи

• Средното от края. Пусни програмата за средния случай с find_latest. Защо средното е същото?
• Сбърканите номера. Ако половината търсения са със сбъркан номер, а другата половина е равномерна, колко проверки са средно при 1 000 поръчки?
• Подредени по номер. Поръчките са подредени по номер. Как може търсенето да спре по-рано, когато номерът го няма? Колко проверки прави тогава за 999?

Тест

Провери се

1. Линейното търсене намира поръчката с първата проверка. Значи ли това, че е O(1)?

Зависи от езикаНе: това е най-добрият случай. Най-лошият е n проверки, затова е O(n)Да, щом е една проверка

2. Защо обикновено се казва най-лошият случай?

Защото е обещание: каквото и да търсят, работата не е повече от товаЗащото е най-честиятЗащото е най-лесен за смятане

3. Всяка от 1 000 поръчки се търси еднакво често. Колко проверки прави линейното търсене средно?

11 000Около 500

4. Клиентите почти винаги търсят последните си поръчки. Как да ускориш търсенето, без да сменяш алгоритъма?

Нищо не помагаТърсиш от края към началотоТърсиш два пъти

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Параметри и return · Общото за всички: атрибути на класа · Времева сложност: броене на стъпки · Big-O: как расте работата
• Продължава в: Сложност по памет · Амортизирана сложност · Линейно търсене · Двоично търсене
• Задачи по темата: Сложност