Почему бы просто не измерить время выполнения программ?
Мы используем нотацию Big O для измерения эффективности программ. Когда говорят об эффективности, все зависит от времени выполнения программы. Если вам интересно, почему бы просто не запустить секундомер, когда мы запускаем нашу программу, и не остановиться, когда она будет завершена, продолжайте читать.
Почему просто не измеряют время выполнения программ?
public static void print1000() {
Instant start = Instant.now();
for(int i = 0; i < 1000; i++) {
System.out.println("Hello, World");
}
Instant finish = Instant.now();
long timeElapsed = Duration.between(start, finish).toMillis();
System.out.println("Milliseconds: " + timeElapsed);
}
Выше пример измерения времени выполнения для этого метода. Я получаю Миллисекунды: 65, а иногда более или менее. Если вы попробуете выполнить этот метод на своей машине, возможно, вы получите другой результат. Потому что ваша машина отличается от моей. Трудно измерить точное время выполнения программы, потому что на разных машинах оно будет разным. это зависит от скорости процессора и других частей вашей машины. Поэтому вместо того, чтобы измерять время выполнения в секундах, мы используем нотацию Big O для измерения скорости роста времени выполнения на основе вводимых данных и с учетом наихудшего сценария.
Измерение в нотации Big O основано на вводе
Если бы мы сравнили время выполнения программы, мы бы измерили в секундах или миллисекундах. Для нотации Big O есть n, который представляет размер ввода. Таким образом, мы можем говорить такие вещи, как
- Время выполнения увеличивается в соответствии с размером ввода - O (n)
- Рост времени выполнения является квадратичным в зависимости от размера ввода - O (n²)
- Рост времени выполнения постоянен для любого размера ввода - O (1)
и так далее.
Давайте посмотрим на примеры (Java):
public void printFirstElement(String[] str) {
System.out.println(str[0]);
}
Временная сложность для приведенного выше примера равна O (1) - постоянное время, потому что на самом деле не имеет значения, насколько велик или мал наш ввод (String [] str), для программы будут выполняться постоянные шаги. выполнить.
public void iterateOver(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
}
Временная сложность этого примера выше O (n) - линейное время, потому что мы печатаем несколько раз или можем сказать, что делаем количество шагов, которое совпадает с размером нашего ввода п. Если числовой ввод будет содержать 1 элемент, нам нужно будет сделать один шаг, а если числа будут иметь 1000 элементов, нам нужно будет сделать 1000 шагов. Итак, нам нужно выполнить n шагов, где n - наш ввод (размер нашего ввода).
public boolean isSevenThere(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == 7) {
return true;
}
}
return false;
}
Временная сложность этой программы составляет O (n) - линейное время. Подождите, нотация Big O зависит от ввода, верно? Если наш входной массив будет выглядеть так [7, 2, 3, 4, 5, 9], он займет всего один шаг, потому что наш метод вернет true в первой итерации, и если наш входной массив [8, 3, 4, 1, 5, 7], тогда это будет O (n), потому что нам нужно перебирать весь массив, пока мы не дойдем до последнего элемента, где 7, и мы сделаем n шаги. Да, это правильно. Важно помнить, что в нотации Big O учитывается наихудший сценарий. В нашем примере наихудшего сценария, когда 7 - последний элемент массива или он не существует, нам нужно сделать n шагов для нашей программы, что составляет O (n) - линейное время.
public void sayHello(int num) {
for (int i = 0; i < num; i++) {
System.out.println("Hello");
}
for (int i = 0; i < num; i++) {
System.out.println("Hi");
}
}
Какова временная сложность этой программы? O (2n)? Нет, это O (n) - линейное время, хотя на самом деле он будет делать в два раза больше шагов каждый раз. Дело в том, что печать в 2 раза больше не зависит от ввода, поэтому мы можем игнорировать такие константы, которые не будут зависеть от размера ввода n.
public void sayHello(int num) {
System.out.println("Hello");
System.out.println("Hello");
System.out.println("Hello");
System.out.println("Hello");
System.out.println("Hello");
for (int i = 0; i < num; i++) {
System.out.println("Hello");
}
}
Здесь O (n) - линейное время. Мы игнорируем части, которые вообще не связаны с вводом. В нашем случае наихудший случай - это когда у нас большой ввод, скажем, num 10000, и 5 статических отпечатков выше станут несущественными по сравнению с частью цикла, где ввод будет определять количество шагов.
public void printStr(String str) {
for (int i = 0; i < 100; i++) {
System.out.println(str);
}
}
Цикл в программе не всегда будет означать O (n) . Временная сложность этой программы равна O (1) - постоянное время. Несмотря на то, что мы печатаем ввод, но количество шагов постоянно и жестко запрограммировано как 100, и неважно, какой ввод будет, он всегда будет занимать 100 шагов.
public boolean isSumTarget(int numArr[], int target) {
for(int i = 0; i < numArr.length; i++) {
for(int j = i + 1; j < numArr.length; j++) {
if(numArr[i] + numArr[j] == target) {
return true;
}
}
}
return false;
}
Временная сложность этой программы O (n²) - квадратичная. Мы повторяем наш массив n раз, поэтому n * n раз.
Некоторые общие временные сложности:
- O (1) - постоянное время
- O (n) - линейное время
- O (log n) - логарифмическое время (двоичный поиск)
- O (n²) - квадратичное время
- O (n³) - кубическое время
Это все, что касается временной сложности с нотацией Big O. Спасибо!
This article is part of the series of articles to learn Java programming language from Tech Lead Academy: 1. Introduction to programming 2. OS, File, and File System 3. Working with terminal 4. Welcome to Java Programming Language 5. Variables and Primitives in Java 6. Methods with Java 7. Java Math Operators and special operators 8. Conditional branching in Java 9. Switch statement in Java 10. Ternary operator in Java 11. Enum in Java 12. String class and its methods in Java 13. Loops in Java 14. Access modifiers in Java 15. Static keyword in Java 16. The final keyword in Java 17. Class and Object in Java 18. Object Oriented Programming in Java 19. OOP: Encapsulation in Java 20. Inheritance in Java 21. Abstraction in Java 22. Polymorphism in Java 23. Overriding vs Overloading in Java 24. OOP Design Principles in Java 25. Array in Java 26. Data Structures with Java 27. Collection framework in Java 28. ArrayList in Java 29. Set in Java 30. Map in Java 31. LocalDate in Java 32. Exception in Java 33. IO in Java 34. Design Patterns 35. Generics in Java 36. Multithreading in java 37. JUnit 38. Big O Notation for coding interviews 39. Top 17 Java coding interview questions for SDET
