Към съдържанието
wannacode

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

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

Проблем

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

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

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

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

Идеята

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

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

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

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

Виж го

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

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

static long checks = 0;


static int FindOrder(int[] ids, int wanted)
{
    for (int i = 0; i < ids.Length; i++)
    {
        checks++;
        if (ids[i] == wanted)
        {
            return i;
        }
    }
    return -1;
}

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

static void Report(int[] ids, int wanted)
{
    checks = 0;
    int at = FindOrder(ids, wanted);
    Console.WriteLine($"{wanted}: {at}, проверки: {checks}");
}

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

int[] ids = new int[1000];
for (int k = 0; k < ids.Length; k++)
{
    ids[k] = 1001 + k;
}
Report(ids, 1001);
Report(ids, 1501);
Report(ids, 999);
Изход
1001: 0, проверки: 1
1501: 500, проверки: 501
999: -1, проверки: 1000

Виж го

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

static long checks = 0;


static int FindOrder(int[] ids, int wanted)
{
    for (int i = 0; i < ids.Length; i++)
    {
        checks++;
        if (ids[i] == wanted)
        {
            return i;
        }
    }
    return -1;
}


static void Report(int[] ids, int wanted)
{
    checks = 0;
    int at = FindOrder(ids, wanted);
    Console.WriteLine($"{wanted}: {at}, проверки: {checks}");
}


int[] ids = new int[8];
for (int k = 0; k < ids.Length; k++)
{
    ids[k] = 1001 + k;
}
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)“, имат предвид най-лошия случай.

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

int[] ids = new int[1000];
for (int k = 0; k < ids.Length; k++)
{
    ids[k] = 1001 + k;
}
long total = 0;
foreach (int wanted in ids)
{
    checks = 0;
    FindOrder(ids, wanted);
    total += checks;
}
Console.WriteLine("Общо: " + total);
Console.WriteLine("Средно: " + (double)total / ids.Length);
Изход
Общо: 500500
Средно: 500.5

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

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

  • Търсената поръчка е първа O(1)
  • Търсената поръчка е в средата O(n)
  • Такава поръчка няма O(n)
Алгоритъмn = 10n = 1000n = 100 000
Търсената поръчка е първа111
Търсената поръчка е в средата650150 001
Такава поръчка няма101000100 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
По-точно, за любопитните

Вграденото търсене в списък е същото линейно търсене. Array.IndexOf, List<T>.IndexOf и Contains минават елементите един по един: O(n) в най-лошия случай. IndexOf връща -1, ако го няма.

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

Пробвай

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

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

int[] ids = { 1001, 1002, 1003, 1004, 1005, 1006 };
foreach (int wanted in new[] { 1004, 1006, 1010 })
{
    checks = 0;
    FindOrder(ids, wanted);
    Console.WriteLine(checks);
}
Отговор

Пробвай

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

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

static int FindOrder(int[] ids, int wanted)
{
    int found = -1;
    for (int i = 0; i < ids.Length; i++)
    {
        checks++;
        if (ids[i] == wanted)
        {
            found = i;
        }
    }
    return found;
}
int[] ids = new int[8];
for (int k = 0; k < ids.Length; k++)
{
    ids[k] = 1001 + k;
}
Report(ids, 1001);
Report(ids, 1005);
Report(ids, 999);
Изход
1001: 0, проверки: 8
1005: 4, проверки: 8
999: -1, проверки: 8

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

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

Упражнение

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

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

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

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

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

Още задачи

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

Тест

Провери се

1. Линейното търсене намира поръчката с първата проверка. Значи ли това, че е O(1)?
2. Защо обикновено се казва най-лошият случай?
3. Всяка от 1 000 поръчки се търси еднакво често. Колко проверки прави линейното търсене средно?
4. Клиентите почти винаги търсят последните си поръчки. Как да ускориш търсенето, без да сменяш алгоритъма?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·