Практически примери на Java за нотификацията Big O

1. Общ преглед

В този урок ще говорим за това какво означава Big O Notation. Ще разгледаме няколко примера, за да проучим ефекта му върху времето за работа на вашия код.

2. Интуицията на Big O Notation

Често чуваме работата на алгоритъм, описан с помощта на Big O Notation.

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

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

3. Алгоритми за постоянно време - O (1)

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

Помислете за тази проста част от кода:

int n = 1000; System.out.println("Hey - your input is: " + n);

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

По същия начин:

int n = 1000; System.out.println("Hey - your input is: " + n); System.out.println("Hmm.. I'm doing more stuff with: " + n); System.out.println("And more: " + n);

Горният пример също е постоянно време. Дори и да отнеме 3 пъти повече време, това не зависи от размера на входа, n. Ние обозначаваме алгоритми с постоянно време, както следва: O (1) . Обърнете внимание, че O (2) , O (3) или дори O (1000) биха означавали едно и също нещо.

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

4. Логаритмични времеви алгоритми - O (log n)

Алгоритмите с постоянно време са (асимптотично) най-бързите. Логаритмичното време е следващото най-бързо. За съжаление те са малко по-сложни за представяне.

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

Важното тук е, че времето за работа нараства пропорционално на логаритъма на входа (в този случай влезте в база 2):

for (int i = 1; i < n; i = i * 2){ System.out.println("Hey - I'm busy looking at: " + i); }

Ако n е 8, изходът ще бъде следният:

Hey - I'm busy looking at: 1 Hey - I'm busy looking at: 2 Hey - I'm busy looking at: 4

Нашият прост алгоритъм работи log (8) = 3 пъти.

5. Линейни времеви алгоритми - O (n)

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

Ако кажем, че нещо нараства линейно, имаме предвид, че то нараства право пропорционално на размера на своите входове.

Помислете за обикновен цикъл за:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); }

Колко пъти се изпълнява това за цикъл? n пъти, разбира се! Не знаем точно колко време ще отнеме това - и не се притесняваме за това.

Това, което знаем е, че простият алгоритъм, представен по-горе, ще нараства линейно с размера на неговия вход.

Ние бихме предпочели време на изпълнение на 0.1N от (1000N + 1000) , но и двете са все още линейни алгоритми; и двамата растат директно пропорционално на размера на вложените средства.

Отново, ако алгоритъмът беше променен на следното:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); System.out.println("Hmm.. Let's have another look at: " + i); System.out.println("And another: " + i); }

Времето за изпълнение все още ще бъде линейно по размер на своя вход, n . Ние обозначаваме линейни алгоритми, както следва: O (n) .

Както при алгоритмите с постоянно време, и ние не се интересуваме от спецификата на изпълнението. O (2n + 1) е същото като O (n) , тъй като Big O Notation се отнася до нарастването на входните размери.

6. N Log N Time Algorithms - O (n log n)

n log n е следващият клас алгоритми. Времето за работа нараства пропорционално на n log n на входа:

for (int i = 1; i <= n; i++){ for(int j = 1; j < n; j = j * 2) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Например, ако n е 8, тогава този алгоритъм ще стартира 8 * log (8) = 8 * 3 = 24 пъти. Дали имаме строго неравенство или не в цикъла for е без значение в името на Big O Notation.

7. Полиномиални времеви алгоритми - O (np)

След това имаме полиномиални времеви алгоритми. Тези алгоритми са дори по-бавни от n log n алгоритми.

Терминът полином е общ термин, който съдържа квадратични (n2) , кубични (n3) , квартични (n4) и др. Функции. Важното е да се знае, че O (n2) е по-бърз от O (n3), което е по-бързо от O (n4) и т.н.

Нека да разгледаме един прост пример за квадратичен времеви алгоритъм:

for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Този алгоритъм ще работи 82 = 64 пъти. Забележете, ако трябва да вложим друг for цикъл, това ще се превърне в алгоритъм O (n3) .

8. Експоненциални времеви алгоритми - O ( k n)

Сега навлизаме в опасна територия; тези алгоритми нарастват пропорционално на някакъв фактор, увеличен от размера на входа.

Например, O (2n) алгоритмите се удвояват с всеки допълнителен вход. Така че, ако n = 2 , тези алгоритми ще работят четири пъти; ако n = 3 , те ще се изпълнят осем пъти (нещо като обратното на логаритмичните времеви алгоритми).

O(3n) algorithms triple with every additional input, O(kn) algorithms will get k times bigger with every additional input.

Let's have a look at a simple example of an O(2n) time algorithm:

for (int i = 1; i <= Math.pow(2, n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

This algorithm will run 28 = 256 times.

9. Factorial Time Algorithms – O(n!)

In most cases, this is pretty much as bad as it'll get. This class of algorithms has a run time proportional to the factorial of the input size.

A classic example of this is solving the traveling salesman problem using a brute-force approach to solve it.

An explanation of the solution to the traveling salesman problem is beyond the scope of this article.

Instead, let's look at a simple O(n!) algorithm, as in the previous sections:

for (int i = 1; i <= factorial(n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

where factorial(n) simply calculates n!. If n is 8, this algorithm will run 8! = 40320 times.

10. Asymptotic Functions

Big O is what is known as an asymptotic function. All this means, is that it concerns itself with the performance of an algorithm at the limit – i.e. – when lots of input is thrown at it.

Big O doesn't care about how well your algorithm does with inputs of small size. It's concerned with large inputs (think sorting a list of one million numbers vs. sorting a list of 5 numbers).

Another thing to note is that there are other asymptotic functions. Big Θ (theta) and Big Ω (omega) also both describes algorithms at the limit (remember, the limit this just means for huge inputs).

To understand the differences between these 3 important functions, we first need to know that each of Big O, Big Θ, and Big Ω describes a set (i.e., a collection of elements).

Here, the members of our sets are algorithms themselves:

  • Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound)
  • Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound)
  • И накрая, Big Θ описва множеството на всички алгоритми, които работят при определена скорост (това е като равенство)

Дефинициите, които сме поставили по-горе, не са математически точни, но ще ни помогнат да разберем.

Обикновено ще чувате неща, описани с помощта на Big O , но не боли да знаете за Big Θ и Big Ω.

11. Заключение

В тази статия обсъдихме обозначението Big O и как разбирането на сложността на алгоритъма може да повлияе на времето за работа на вашия код.

Чудесна визуализация на различните класове на сложност можете да намерите тук.

Както обикновено, кодовите фрагменти за този урок могат да бъдат намерени в GitHub.