Алгоритми и как да анализираме тяхната сложност

Алгоритмите участват в почти всички задачи, които изпълняваме ежедневно. Ние изпълняваме много от тях на „автоматично“, без дори да осъзнаваме „за какво“ се използват или „как“ ги използваме. В разработката на софтуер не е толкова различно. Но, какви са алгоритмите, така или иначе? И защо е важно да се анализира тяхната сложност?

Нека разберем! :)

Какво е алгоритъм?

Набор от стъпки, необходими за изпълнение на задача.

Компютърните програми не са единствените неща, които изпълняват алгоритми, те също се изпълняват и прилагат от нас, хората.

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

  • Измий си зъбите
  • Вземам вана
  • готвач
  • Карайте до работа от вкъщи

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

  1. Качете се в колата ми
  2. Закарайте се до къщата на приятел, за да ги подкарате
  3. Карай до офиса, където работя
  4. Паркирайте колата ми на гаража

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

Сега помислете за необходимия набор от стъпки, които предприемате, за да изпълните същата задача. Вероятно са малко по-различни от моите. Нашите алгоритми може да са различни, но нашата цел е същата.

Компютърните програми не са твърде различни: има различни алгоритми, които могат да се използват за изпълнение на редица задачи. Често ние не се занимаваме с това какви са те, просто ги използваме (включително и аз).

Например как трябва да изглежда алгоритъмът, използван от Waze и Google Maps, този, който изчислява най-добрия маршрут между две локации? Какво ще кажете за алгоритъма на Netflix, който предлага филми и сериали въз основа на това, което сте гледали?

Лично аз не можах да ти кажа. Аз обаче знам, че те са ефективни. И ефективността е стандартът, който използваме за анализ на сложността на един алгоритъм.

Какво представлява сложността на алгоритъма?

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

По принцип алгоритмите се оценяват от тяхното потребление и на време, и на пространство, но в този пост ще се спра само на времевата сложност.

Анализът на сложността на времето ни позволява да определим как да се държи един алгоритъм при увеличаване на входните му елементи. Можем да имаме представа за времето, което ще отнеме за обработка на 10, 100 или 1000 елемента.

И защо е важен този анализ?

  • Да се ​​определи кой алгоритъм е най-ефективен;
  • Да може да разработи по-ефективни алгоритми;
  • За да можете да анализирате дали библиотеката на алгоритъма или дори е действителният език са ефективни.

В обобщение, ефективността е въпросът!

Време сложност

Времето, необходимо за приключване на дейност.

Можем да започнем да анализираме времето с метода за броене на честотата, който в общи линии отчита броя на изпълненията на машинна инструкция. Всяка стъпка (инструкция) е назначена единица за време, започвайки с 1.

Времето, което алгоритъмът изразходва, се изразява с функцията f (n), където n представлява размера на данните.

Резултатът от анализ се изразява, както следва:

([функция, която изразява време]) = [Сума от времевите единици]

Сега нека анализираме някои алгоритми, за да разберем как работи това в действителност.

Първата функция събира две цели числа:

Можем да видим, че за споменатата задача реализираният алгоритъм изпълнява само една стъпка: сумирането на две числа. Тъй като ние приписваме стойност за всяка стъпка, резултатът е f (n) = 1.

Нека разгледаме следващия пример, който е алгоритъм, който разделя цяло число от друго цяло число:

Въпреки че е математическа операция, подобна на сумирането, алгоритъмът съдържа повече стъпки, защото трябва да провери дали делителят е 0; ако това е така, разделението няма да бъде осъществено. Тъй като имаме общо четири стъпки и на всяка от тях е присвоена стойност 1, резултатът е f (n) = 4.

Следващият алгоритъм обобщава всички елементи от списък с цели числа:

В този алгоритъм една от стъпките включва инструкция за повторение; това означава, че кодът вътре в for ще бъде изпълнен няколко пъти. Тъй като броят на изпълненията зависи от размера на данните, ние приписваме стойността n като единица време. Резултатът е f (n) = 2n + 3.

Следващият алгоритъм добавя сумата от един списък със сумата от втори списък.

В резултат имаме f (n) = 2n² + 2n + 3.

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

Обикновено, когато анализираме алгоритъм, се опитваме да открием поведението му, когато има много елементи за обработка. Именно в тези ситуации трябва да намерим преобладаващия термин от сумата от единиците за време.

Например, какъв е преобладаващият термин от сумата на третия алгоритъм?

f (n) = 2n + 3

В този случай преобладаващият термин в 2 * n и ще обясня защо!

Във всяка ситуация, когато n е по-голяма от 1 (n> 1), продуктът (резултатът от умножение) вече ще струва повече от втория член на сумата.

Тествайте нещо: заменете n с всяко цяло, по-голямо от 1, и извършете умножението.

Какво ще кажете за преобладаващия термин от сумата на последния алгоритъм?

f (n) = 2n² + 2n + 3

В този случай преобладаващият срок е 2 * n², тъй като когато n> 1, продуктът винаги ще бъде по-голям от втория и третия член на сумата. Давай, тествай го!

Ерго, има по-често срещан начин, така да се каже, да се анализира сложността на алгоритмите, при които константи и по-малко значими термини не се вземат под внимание. Този метод се нарича асимптотична сложност.

Това е мястото, в което влиза в сила редът на сложността, известен още като Notation-O или Big-O.

Нотация с големи размери

Използва се за класифициране на алгоритъм, отчитащ темпа на растеж на операциите с увеличаване на броя на обработените елементи.

Нотацията Big-O също така определя функция, която изразява сложността на времето на един алгоритъм. За тази цел n се използва като функция на буквата O.

Най-често срещаните класове са:

  • O (1) - Постоянно, броят на операциите не се увеличава с увеличаването на броя на елементите
  • O (log n) - логаритмичен, брой операции е по-малък от броя на елементите
  • O (n) - Линейно, броят на операциите се увеличава пропорционално на броя на елементите
  • O (n²) Квадратна, броят на операциите ще бъде по-голям от броя на елементите
  • O (2 ^ n) - Експоненциален, броят на операциите се увеличава бързо в сравнение с броя на елементите
  • O (n!) - Факторно, броят на операциите се увеличава много, много бързо, дори и за малък брой елементи

По-долу имаме графика, която илюстрира степента на растеж на операциите x Количество елементи:

Графиката е класифицирана, както следва:

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

Сега, ние ще използваме Big-O нотация, за да категоризираме алгоритмите, които бяха споменати по-рано, винаги използвайки техния преобладаващ термин, за да ни ръководи.

Първият алгоритъм доведе до f (n) = 1; което означава, че независимо от увеличението на елементите, алгоритъмът изпълнява само една операция. По този начин можем да класифицираме алгоритъма като Constant - O (1).

Вторият алгоритъм доведе до f (n) = 4; което означава, че независимо от увеличението на елементите, алгоритъмът ще извърши четири операции. По този начин можем да класифицираме този алгоритъм като Константа - O (1).

Резултатът от третия алгоритъм беше f (n) = 2n + 3; което означава, че броят на операциите ще нараства пропорционално на броя на елементите, виждайки как n служи като променлива в тази функция. По този начин можем да определим този алгоритъм като линеен - O (n).

Резултатът от последния алгоритъм доведе до f (n) = 2n² + 2n + 3, което означава, че броят на операциите ще се увеличи повече от броя на елементите. В този случай n също служи като променлива, но тя е повдигната до втората мощност (квадрат). По този начин можем да определим този алгоритъм като квадратичен - O (n²).

Таблицата по-долу илюстрира растежа на броя на операциите, тъй като е свързана с нарастването на броя на елементите.

Забележете, че в експоненциален алгоритъм 16 елемента ще доведат до поне 65 55536 операции. Доста смущаващо, нали?

Като цяло процесът на анализ е същият, както ние правихме: преброяване на броя стъпки и идентифициране на преобладаващия термин.

Някои тенденции, които можем да наблюдаваме:

  • Алгоритмите, които нямат цикъл на повторение, са склонни да бъдат постоянни - O (1)
  • Алгоритмите, които имат цикъл на повторение, стига да не са вложени, са склонни да бъдат линейни - O (n)
  • Алгоритмите, които имат две вложени вериги за повторение, са склонни да бъдат квадратични - O (n²)
  • Директният достъп до индекса на масива обикновено е O (1) (константа)
  • Средно методите за разширение на списъка са O (n). Например: всяка, сума и филтър.
  • Алгоритмите за сортиране като сортиране на балончета, сортиране на вмъкване и сортиране на селекцията обикновено са O (n²).

Знанието как да класифицираме алгоритмите ни дава способността да преценяваме ефективността или неефективността на алгоритъма. Разбира се, не можем да измерим точното му време на работа за секунди, минути или часове. За целта трябва да бъде изпълнено, измерено и съответно променено. Представете си, че правите това за алгоритми, които отнемат часове или дори дни? Няма шанс!

Надявам се, че съм изпълнил целта на този пост, който беше да дам преглед на алгоритмите и техния анализ, използвайки методите за броене на честотата и Big-O.

Оставих някои справки по-долу като допълнителен материал за четене!

Препратки:

Vídeos 1 до 1.7

Искате да внесете иновации на пазара на заеми чрез технологиите? Винаги търсим нови хора, които да се присъединят към екипа ни!

Вижте нашите отвори тук.