What is big o notation in java

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

Изучение производительности алгоритмов — или алгоритмической сложности — относится к областиalgorithm analysis. Анализ алгоритма отвечает на вопрос о том, сколько ресурсов, таких как дисковое пространство или время, потребляет алгоритм.

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

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

Как этот размер входного алгоритма влияет на время его работы? Key to understanding Big O is understanding the rates at which things can grow. Рассматриваемая скорость здесьtime taken per input size.

Рассмотрим этот простой кусок кода:

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 раза больше времени, itdoesn’t depend on the size of the input, n. Мы обозначаем алгоритмы с постоянным временем следующим образом:O(1). Обратите внимание, чтоO(2),O(3) или дажеO(1000) будут означать одно и то же.

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

4. Алгоритмы логарифмического времени —O(log n)с

Алгоритмы с постоянным временем (асимптотически) самые быстрые. Logarithmic time is the next quickest. К сожалению, представить их немного сложнее.

Одним из распространенных примеров алгоритма логарифмического времени является алгоритмbinary search. Чтобы увидеть, как реализовать двоичный поиск в Java,click here.

Здесь важно то, чтоrunning time grows in proportion to the logarithm of the input (in this case, log to the base 2):

Если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)с

После алгоритмов логарифмического времени мы получаем следующий самый быстрый класс:linear time algorithms.

Если мы говорим, что что-то растет линейно, мы имеем в виду, что оно растет прямо пропорционально размеру его входных данных.

Придумайте простой цикл for:

Сколько раз это делается для цикла? n раз, конечно! Мы не знаем точно, сколько времени это займет, и нас это не волнует.

Что мы действительно знаем, так это то, что простой алгоритм, представленный выше, будет линейно расти с размером его входных данных.

Мы предпочли бы время выполнения0.1n, чем(1000n + 1000), но оба алгоритма по-прежнему являются линейными; они оба растут прямо пропорционально размеру их ресурсов.

Опять же, если алгоритм был изменен на следующее:

Время выполнения по-прежнему будет линейным по размеру входных данныхn. Обозначим линейные алгоритмы следующим образом:O(n).

Как и в случае с алгоритмами постоянного времени, мы не заботимся о специфике среды выполнения. O(2n+1) is the same as O(n), поскольку нотация Big O занимается ростом размеров входных данных.

6. N Log N Time Algorithms —O(n log n)с

n log n is the next class of algorithms. Время работы увеличивается пропорциональноn log n входа:

Например, еслиn равно 8, то этот алгоритм будет выполняться8 * log(8) = 8 * 3 = 24 раз. Имеем ли мы строгое неравенство или нет в цикле for, не имеет значения для обозначения Big O.

7. Полиномиальные временные алгоритмы —O(n p )с

Далее у нас есть алгоритмы с полиномиальным временем. Эти алгоритмы даже медленнее, чем алгоритмыn log n.

Термин полином — это общий термин, который содержит квадратичный(n 2 ), кубический(n 3 ), четвертый(n 4 ) и т. Д. функции. What’s important to know is that O(n 2 ) is faster than O(n 3 ) which is faster than O(n 4 ), etc.

Давайте посмотрим на простой пример алгоритма квадратичного времени:

Этот алгоритм будет выполняться8 2 = 64 раз. Обратите внимание: если бы мы вложили еще один цикл for, это стало бы алгоритмомO(n 3 ).

8. Экспоненциальные временные алгоритмы —O(k _ n ) _

Теперь мы попадаем на опасную территорию; Эти алгоритмы растут пропорционально некоторому коэффициенту, который определяется степенью входного размера.

Например,O(2 n ) algorithms double with every additional input. Итак, еслиn = 2, эти алгоритмы будут выполняться четыре раза; еслиn = 3, они будут выполняться восемь раз (что-то вроде противоположности алгоритмов логарифмического времени).

АлгоритмыO(3 n ) утраиваются с каждым дополнительным вводом, алгоритмыO(k n ) будут увеличиваться в k раз с каждым дополнительным вводом.

Давайте посмотрим на простой пример временного алгоритмаO(2 n ):

Этот алгоритм будет выполняться2 8 = 256 раз.

9. Факториальные временные алгоритмы —O(n!)с

В большинстве случаев это почти так же плохо, как и могло случиться. Этот класс алгоритмов имеет время выполнения, пропорциональноеfactorial размера ввода.

Классическим примером этого является решение проблемыtraveling salesman с использованием метода грубой силы для ее решения.

Объяснение решения проблемы коммивояжера выходит за рамки данной статьи.

Вместо этого давайте рассмотрим простой алгоритмO(n!), как в предыдущих разделах:

гдеfactorial(n) просто вычисляет n !. Если n равно 8, этот алгоритм будет выполняться8! = 40320 раз.

10. Асимптотические функции

Big O is what is known as an asymptotic function. Все это означает, что он заботится о производительности алгоритмаat the limit — т.е. — когда на него брошено много информации.

Big O не заботится о том, насколько хорошо ваш алгоритм работает с входными данными небольшого размера. Это связано с большими входными данными (подумайте о сортировке списка из миллиона номеров по сравнению с сортировка списка из 5 номеров).

Также следует отметить, чтоthere are other asymptotic functions. Big Θ (theta) и Big Ω (omega) также оба описывают алгоритмы на пределе (помните,the limit это означает только для огромных входных данных).

Чтобы понять разницу между этими тремя важными функциями, нам сначала нужно знать, что каждая из Big O, Big Θ и Big Ω описываетset (то есть набор элементов).

Здесь члены наших наборов сами являются алгоритмами:

• Big O описывает набор всех алгоритмов, которые запускаютno worse выше определенной скорости (это верхняя граница)
• И наоборот, Big Ω описывает набор всех алгоритмов, которые выполняютno better, превышающую определенную скорость (это нижняя граница).
• Наконец, Big Θ описывает набор всех алгоритмов, которые запускаютat с определенной скоростью (это похоже на равенство)

Приведенные выше определения математически неточны, но они помогут нашему пониманию.

Usually, you’ll hear things described using Big O, но знать о Big Θ и Big Ω не помешает.

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

В этой статье мы обсудили нотацию Big O и то, какunderstanding the complexity of an algorithm can affect the running time of your code.

Отличная визуализация разных классов сложностиcan be found here.

Как обычно, фрагменты кода для этого руководства можно найтиover on GitHub.

Источник

What is the Java Big O Notation

The “Big O Notation” is also termed “asymptotic notation”. These notations come into effect while dealing with different sorts of algorithms. It is such that these notations represent the time taken by an algorithm to execute when the input tends towards a certain or a limiting value, there are different asymptotic notations in which the time complexities of algorithms are measured which will be discussed in this article.

What is the Java “Big O Notation”?

The “Big O Notation” is used to fetch the “Time complexity”. Time complexity computes the time to execute an algo­rithm. It is computed by counting the implemented functionalities. It is vital to analyze the reason for the execution/run time as it is only dependent on the algorithm and its input. In such a situation, the “Big O Notation” comes into effect that analyzes the functionalities based on their growth rates.

Advantages of “Big O Notation”

• The “Big O Notation” is vital for analyzing the algorithm’s efficiency.
• When the algorithm is executed on multiple systems, its performance varies. Using this notation, the developer can opt for an algorithm whose performance is not affected much comparatively by the number of inputs.

Example 1: Time Complexity of “O(1)”

This example executes in “O(1)” time with respect to its input. The defined array could be “1” or “n” items, but the functionality will require just one step:

public class Bignotation {
public static void main ( String [ ] args ) {
int array [ ] = { 1 , 2 , 3 } ;
System . out . println ( «First Array Item -> » + array [ 0 ] ) ;
} }

In this code, initialize the stated array and retrieve its first value via indexing i.e., “[0]”, thereby requiring only one step.

The first array element is retrieved successfully.

Example 2: Time Complexity of “O(n)”

In this example, the applied functionality executes in “O(n)” time, where “n” is the number of array elements. It is such that if the array has 10 items, the loop will execute 10 times to print all of them and so on:

public class Bignotation {
public static void main ( String [ ] args ) {
int array [ ] = { 1 , 2 , 3 } ;
for ( int i = 0 ; i < array. length ; i ++ )
System . out . println ( array [ i ] ) ;
} }

According to this block of code, likewise, initialize the stated array. In the next step, use the “for” loop to iterate the array elements and display them based on the applied “length” property.

Example 3: Time Complexity of “O(m * n)”

This particular example finds the time complexity for the nested loops. It is such that if the outer loop executes once, the inner loop will execute “n” times, giving a series as “n + n + n….m” times which can be written as “m * n”:

public class Bignotation {
public static void main ( String [ ] args ) {
int x = 0 ;
int m = 2 ;
int n = 3 ;
for ( int i = 0 ; i < m ; i ++ ) {
for ( int j = 0 ; j < n ; j ++ ) {
x = x + j ;
System . out . print ( x + » » ) ;
}
System . out . println ( ) ;
}
} }

In this code implementation, the nested “for” loops are applied such that upon each iteration of the outer “for” loop, the inner loop executes completely. This resultantly returns “m * n” values.

As seen, the corresponding number of values i.e., “2 * 3 = 6” is returned appropriately.

Example 4: Time Complexity of “O(log2 N)”

If there are two iterators in which the outer one executes “N/2” times, the time complexity of a loop is evaluated as “O(log N)”. Additionally, if the iterator is divided or multiplied by a constant “x”, then the time complexity is considered as “O(logx N)” which is the case here:

public class Bignotation {
public static void main ( String [ ] args ) {
int x = 4 , y = 0 ;
for ( int i = x / 2 ; i for ( int j = 2 ; j j = j * 2 ) {
System . out . print ( y + » » ) ;
y = y + x / 2 ;
} }
} }

In this case, the upper-discussed concept is followed in which the outer loop runs for “x/2” times. The inner loop, however, executes “log N” times for all “i”.

Conclusion

The “Big O Notation” is utilized to fetch the “Time complexity”. These time complexities can be “O(1)”, “O(n)”, “O(m*n)”, or “O(log2 N)” etc. These notations are helpful in analyzing various sorts of implemented code algorithms. This article discussed the Java “Big O Notation”.

About the author

Umar Hassan

I am a Front-End Web Developer. Being a technical author, I try to learn new things and adapt with them every day. I am passionate to write about evolving software tools and technologies and make it understandable for the end-user.

Источник