Въведение в сложността на времето на алгоритмите

В компютърните науки анализът на алгоритмите е много важна част. Важно е да се намери най-ефективният алгоритъм за решаване на проблем. Възможно е да имате много алгоритми за решаване на проблем, но предизвикателството тук е да изберете най-ефективния.

Въпросът е сега, как можем да разпознаем най-ефективния алгоритъм, ако имаме набор от различни алгоритми? Тук възниква концепцията за сложността на пространството и времето на алгоритмите. Сложността на пространството и времето действа като скала за измерване на алгоритмите. Сравняваме алгоритмите въз основа на тяхното пространство (обем памет) и сложност на времето (брой операции).

Общият обем на паметта на компютъра, използван от алгоритъма, когато се изпълнява, е сложността на пространството на този алгоритъм. В тази статия няма да обсъждаме сложността на пространството (за да я направим малко по-малка).

Сложност във времето

И така, сложността във времето е броят на операциите, които алгоритъмът изпълнява, за да изпълни задачата си (като се има предвид, че всяка операция отнема еднакво време). Алгоритъмът, който изпълнява задачата при най-малък брой операции, се счита за най-ефективен от гледна точка на сложността на времето. Сложността на пространството и времето обаче се влияе и от фактори като вашата операционна система и хардуер, но ние не ги включваме в тази дискусия.

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

Проблемът е в търсенето. Трябва да търсим елемент в масив (в този проблем ще приемем, че масивът е сортиран във възходящ ред). За да разрешим този проблем, имаме два алгоритма:

1. Линейно търсене.

2. Двоично търсене.

Да предположим, че масивът съдържа десет елемента и трябва да намерим числото десет в масива.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

Линейният алгоритъм за търсене ще сравнява всеки елемент от масива с цифрата search_digit . Когато открие search_digit в масива, той ще върне true .

Сега нека преброим броя на операциите, които извършва. Тук отговорът е 10 (тъй като сравнява всеки елемент от масива). И така, линейното търсене използва десет операции за намиране на дадения елемент (това са максималният брой операции за този масив; в случай на линейно търсене това е известно и като най-лошия случай на алгоритъм).

По принцип линейното търсене ще отнеме n брой операции в най-лошия си случай (където n е размерът на масива).

Нека разгледаме двоичния алгоритъм за търсене за този случай.

Бинарното търсене може лесно да бъде разбрано от този пример:

Източник: Learneroo

Ако се опитаме да приложим тази логика върху нашия проблем, първо ще сравним search_digit със средния елемент на масива, който е 5. Сега, тъй като 5 е по-малко от 10, тогава ще започнем да търсим search_digit в елементите на масива по-голям от 5, по същия начин, докато получим желания елемент 10.

Сега се опитайте да преброите броя операции, извършени от двоичното търсене, за да намерите желания елемент. Отне приблизително четири операции. Това беше най-лошият случай за двоично търсене. Това показва, че съществува логаритмична връзка между броя на извършените операции и общия размер на масива.

брой операции = log (10) = 4 (приблизително)

за основа 2

Можем да обобщим този резултат за двоично търсене като:

За масив с размер n броят на операциите, извършени от двоичното търсене, е: log (n)

Нотацията „Голямото О“

В горните твърдения видяхме, че за масив с размер n линейното търсене ще извърши n операции за завършване на търсенето. От друга страна, двоичното търсене извърши log (n) брой операции (и двете за най-лошите им случаи). Можем да представим това като графика ( оста x : брой елементи, оста y : брой операции).

Източник: Techtud

От фигурата става съвсем ясно, че скоростта, с която се увеличава сложността при линейно търсене, е много по-бърза от тази при двоично търсене.

Когато анализираме алгоритъм, използваме нотация, за да представим неговата сложност във времето и тази нотация е Big O нотация.

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

Сложността на времето или обозначенията Big O за някои популярни алгоритми са изброени по-долу:

  1. Двоично търсене: O (log n)
  2. Линейно търсене: O (n)
  3. Бързо сортиране: O (n * log n)
  4. Сортиране на избора: O (n * n)
  5. Пътуващ продавач: O (n!)

Заключение

Наистина оценявам усилията ви, ако все още четете тази статия. Сега сигурно си мислите - защо сложността на времето е толкова важна за разбиране?

Знаем, че за малък брой елементи (да речем 10), разликата между броя на операциите, извършени чрез двоично търсене и линейно търсене, не е толкова голяма. Но в реалния свят в повечето случаи се справяме с проблеми, които имат големи количества данни.

Например, ако имаме 4 милиарда елемента, които да търсим, тогава в най-лошия случай линейното търсене ще отнеме 4 милиарда операции, за да изпълни задачата си. Двоичното търсене ще изпълни тази задача само за 32 операции. Това е голяма разлика. Сега нека приемем, че ако една операция отнема 1 ms за завършване, тогава бинарното търсене ще отнеме само 32 ms, докато линейното търсене ще отнеме 4 милиарда ms (това е приблизително 46 дни). Това е значителна разлика.

Това е причината, поради която изучаването на сложността във времето става важно, когато става въпрос за толкова голямо количество данни.

Ресурси

Grokking Algorithms - от Aditya Y Bhargava

Въведение в Big O нотация и сложност на времето - от CS Dojo