Инструменты пользователя
basics_of_algorithms:algorithmic_complexity
Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия | ||
|
basics_of_algorithms:algorithmic_complexity [2023/10/04 14:44] werwolf [Оптимизация] |
basics_of_algorithms:algorithmic_complexity [2023/10/20 16:33] (текущий) werwolf [Выводы] |
||
|---|---|---|---|
| Строка 50: | Строка 50: | ||
| quickSort(items, 0, items.length - 1); | quickSort(items, 0, items.length - 1); | ||
| }; | }; | ||
| - | |||
| const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]; | const items = [86, 66, 44, 77, 56, 64, 76, 39, 32, 93, 33, 54, 63, 96, 5, 41, 20, 58, 55, 28]; | ||
| Строка 59: | Строка 58: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 98: | Строка 96: | ||
| print(end - start); # <= 0.20 миллисекунд | print(end - start); # <= 0.20 миллисекунд | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 162: | Строка 160: | ||
| print_r($end - $start); // <= 0.20 миллисекунд | print_r($end - $start); // <= 0.20 миллисекунд | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 218: | Строка 216: | ||
| System.out.println(end - start); // 0.2 миллисекунд | System.out.println(end - start); // 0.2 миллисекунд | ||
| </code> | </code> | ||
| - | </details> | ||
| - | Алгоритм быстрой сортировки мы уже разбирали. Единственное, что нам пока не встречалось — вызов метода ''performance.now()''. | ||
| - | Performance — это объект в глобальной области видимости, который используют для измерения производительности. Метод ''now()'' возвращает количество миллисекунд с момента старта браузера. Можно запустить этот метод, сохранить значения до запуска кода и после его завершения, и вычесть одно из другого — и тогда мы узнаем, сколько миллисекунд работал наш код. | + | </details> Алгоритм быстрой сортировки мы уже разбирали. Единственное, что нам пока не встречалось — вызов метода ''performance.now()''. |
| + | |||
| + | Performance — это объект в глобальной области видимости, который используют для измерения производительности. Метод ''now()'' возвращает количество миллисекунд с момента старта браузера. Можно запустить этот метод, сохранить значения до запуска кода и после его завершения, и вычесть одно из другого — и тогда мы узнаем, сколько миллисекунд работал наш код. | ||
| Чтобы сравнить два алгоритма, надо упорядочить точно такой же массив с помощью алгоритма выбора: | Чтобы сравнить два алгоритма, надо упорядочить точно такой же массив с помощью алгоритма выбора: | ||
| Строка 247: | Строка 245: | ||
| </code> | </code> | ||
| - | + | <details> <summary>Python</summary> | |
| - | <details> | + | |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 268: | Строка 264: | ||
| print(end - start) # <= 0.09 миллисекунды | print(end - start) # <= 0.09 миллисекунды | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 306: | Строка 302: | ||
| print_r($end - $start); // <= 0.09 миллисекунды | print_r($end - $start); // <= 0.09 миллисекунды | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 336: | Строка 332: | ||
| System.out.println(end - start); // 0.09 миллисекунд | System.out.println(end - start); // 0.09 миллисекунд | ||
| </code> | </code> | ||
| - | </details> | ||
| - | Оценим скорость кода выше: | ||
| - | * Быстрая сортировка — 0,20 миллисекунд | + | </details> Оценим скорость кода выше: |
| - | * Сортировка выбором — 0,09 миллисекунд | + | |
| + | * Быстрая сортировка — 0,20 миллисекунд | ||
| + | * Сортировка выбором — 0,09 миллисекунд | ||
| Результат выглядит странно. Раз уж быструю сортировку назвали быстрой, то время ее выполнения должно быть меньше, чем у сортировки выбором. Здесь дело в том, что результаты однократного измерения ненадежны. Нужно измерить производительность алгоритмов несколько раз подряд на одних и тех же данных. Можем получить такой результат: | Результат выглядит странно. Раз уж быструю сортировку назвали быстрой, то время ее выполнения должно быть меньше, чем у сортировки выбором. Здесь дело в том, что результаты однократного измерения ненадежны. Нужно измерить производительность алгоритмов несколько раз подряд на одних и тех же данных. Можем получить такой результат: | ||
| - | * Быстрая сортировка — 0,21 миллисекунда | + | * Быстрая сортировка — 0,21 миллисекунда |
| - | * Сортировка выбором — 0,12 миллисекунд | + | * Сортировка выбором — 0,12 миллисекунд |
| Или даже такой: | Или даже такой: | ||
| - | * Быстрая сортировка — 0,16 миллисекунд | + | * Быстрая сортировка — 0,16 миллисекунд |
| - | * Сортировка выбором — 0,17 миллисекунд | + | * Сортировка выбором — 0,17 миллисекунд |
| Разброс может быть достаточно большим. Дело в том, что на производительность нашей программы влияет множество случайных факторов: другие запущенные программы на компьютере, режим энергосбережения и так далее. | Разброс может быть достаточно большим. Дело в том, что на производительность нашей программы влияет множество случайных факторов: другие запущенные программы на компьютере, режим энергосбережения и так далее. | ||
| Строка 373: | Строка 369: | ||
| </code> | </code> | ||
| - | + | <details> <summary>Python</summary> | |
| - | <details> | + | |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 394: | Строка 388: | ||
| average_performance(selection_sort(items[:]), 10) # 0.0699999988079 | average_performance(selection_sort(items[:]), 10) # 0.0699999988079 | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 426: | Строка 420: | ||
| averagePerformance(fn() => selectionSort([...$items]), 10); // 9.7 | averagePerformance(fn() => selectionSort([...$items]), 10); // 9.7 | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 452: | Строка 446: | ||
| App.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 10);// 0.069 | App.averagePerformance(() -> selectionSort(Arrays.copyOf(items, items.length)), 10);// 0.069 | ||
| </code> | </code> | ||
| - | </details> | ||
| - | Возможно вы не знакомы с конструкцией ''%%[…items]%%'', которая встречается в этом коде. Она позволяет сделать копию массива ''items''. Без копии мы при первом же вызове функции ''selectionSort'' упорядочим массив ''items'', и последующие вызовы будут измерять скорость сортировки уже упорядоченного массива. | ||
| - | У функции ''averagePerformance'' два параметра: | + | </details> Возможно вы не знакомы с конструкцией ''<nowiki>[…items]</nowiki>'', которая встречается в этом коде. Она позволяет сделать копию массива ''items''. Без копии мы при первом же вызове функции ''selectionSort'' упорядочим массив ''items'', и последующие вызовы будут измерять скорость сортировки уже упорядоченного массива. |
| - | * Функция, чью производительность мы хотим измерить | + | У функции ''averagePerformance'' два параметра: |
| - | * Количество раз, когда мы хотим ее запустить | + | |
| - | Мы видим, что среднее время выполнения может заметно отличаться от времени, измеренного один раз — на 30% в нашем случае. Значит ли это, что теперь у нас в руках есть надежный способ сравнения алгоритмов? Кажется, что да. Но мы пока так и не выяснили, почему быстрая сортировка такая медленная по сравнению с сортировкой выбором. | + | * Функция, чью производительность мы хотим измерить |
| + | * Количество раз, когда мы хотим ее запустить | ||
| + | |||
| + | Мы видим, что среднее время выполнения может заметно отличаться от времени, измеренного один раз — на 30% в нашем случае. Значит ли это, что теперь у нас в руках есть надежный способ сравнения алгоритмов? Кажется, что да. Но мы пока так и не выяснили, почему быстрая сортировка такая медленная по сравнению с сортировкой выбором. | ||
| Продолжим искать причину и сравним время выполнения разных сортировок на массиве из ста элементов: | Продолжим искать причину и сравним время выполнения разных сортировок на массиве из ста элементов: | ||
| Строка 470: | Строка 464: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 478: | Строка 471: | ||
| average_performance(quick_sort(items[:]), 10) # 0.19 | average_performance(quick_sort(items[:]), 10) # 0.19 | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 490: | Строка 483: | ||
| averagePerformance(fn() => quickSort([...$items]), 10); // 65 | averagePerformance(fn() => quickSort([...$items]), 10); // 65 | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 501: | Строка 494: | ||
| App.averagePerformance(() -> quickSort(Arrays.copyOf(items, items.length)), 10);// 0.19 | App.averagePerformance(() -> quickSort(Arrays.copyOf(items, items.length)), 10);// 0.19 | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| Строка 511: | Строка 505: | ||
| Идея оценки «в целом» пришла к нам из математики, где есть похожая задача — нужно оценивать порядок роста функций. Математики могут точно рассчитать скорость возрастания функции в любой точке, но эта информация может оказаться не очень полезной. Сравним графики двух функций: | Идея оценки «в целом» пришла к нам из математики, где есть похожая задача — нужно оценивать порядок роста функций. Математики могут точно рассчитать скорость возрастания функции в любой точке, но эта информация может оказаться не очень полезной. Сравним графики двух функций: | ||
| - | {{ :basics_of_algorithms:image_processing20231003-35-owhrjh.png |}} | + | {{ :basics_of_algorithms:image_processing20231003-35-owhrjh.png }} |
| Кажется, что синяя функция больше, чем, красная. Но если посмотреть на те же графики в другом масштабе, картина изменится: | Кажется, что синяя функция больше, чем, красная. Но если посмотреть на те же графики в другом масштабе, картина изменится: | ||
| - | {{ :basics_of_algorithms:image_processing20231003-26-x31ief.png |}} | + | {{ :basics_of_algorithms:image_processing20231003-26-x31ief.png }} |
| Красная функция растет гораздо быстрее и почти сразу становится больше синей. С алгоритмами возникает та же проблема: на одном наборе данных первый алгоритм физически будет быстрее второго, на многих других наборах он может оказаться гораздо медленнее. Синяя функция на графике — это прямая линия, а красная — это парабола. | Красная функция растет гораздо быстрее и почти сразу становится больше синей. С алгоритмами возникает та же проблема: на одном наборе данных первый алгоритм физически будет быстрее второго, на многих других наборах он может оказаться гораздо медленнее. Синяя функция на графике — это прямая линия, а красная — это парабола. | ||
| Строка 525: | Строка 519: | ||
| ===== Линейная сложность ===== | ===== Линейная сложность ===== | ||
| - | Чтобы определить временную сложность алгоритма, программисты ставят мысленный эксперимент. Предположим, что мы точно измерили время работы алгоритма на одном массиве, а потом увеличили этот массив в десять раз. Как увеличится время работы алгоритма? Если время работы алгоритма также увеличится в десять раз, то речь идет **о линейной сложности** — на графике она бы описывалась прямой линией. | + | Чтобы определить временную сложность алгоритма, программисты ставят мысленный эксперимент. Предположим, что мы точно измерили время работы алгоритма на одном массиве, а потом увеличили этот массив в десять раз. Как увеличится время работы алгоритма? Если время работы алгоритма также увеличится в десять раз, то речь идет **о линейной сложности** — на графике она бы описывалась прямой линией. |
| Типичный линейный алгоритм — поиск минимального элемента в массиве: | Типичный линейный алгоритм — поиск минимального элемента в массиве: | ||
| Строка 543: | Строка 537: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 556: | Строка 549: | ||
| return minimum | return minimum | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 577: | Строка 570: | ||
| }; | }; | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 597: | Строка 590: | ||
| } | } | ||
| </code> | </code> | ||
| - | </details> | + | |
| - | Это простой алгоритм. Мы просматриваем элементы массива по одному и сравниваем с уже найденным. Если новый элемент оказывается меньше минимума, он становится новым минимумом. В самом начале в качестве минимума выбираем самый первый элемент массива с индексом 0. Функция состоит из двух смысловых элементов. Первый элемент — инициализация: | + | </details> Это простой алгоритм. Мы просматриваем элементы массива по одному и сравниваем с уже найденным. Если новый элемент оказывается меньше минимума, он становится новым минимумом. В самом начале в качестве минимума выбираем самый первый элемент массива с индексом 0. Функция состоит из двух смысловых элементов. Первый элемент — инициализация: |
| <code javascript> | <code javascript> | ||
| Строка 604: | Строка 597: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| minimum = items[0] | minimum = items[0] | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | + | <details> <summary>PHP</summary> | |
| - | <details> | + | |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 621: | Строка 612: | ||
| $minimum = $items[0]; | $minimum = $items[0]; | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| var minimum = items[0]; | var minimum = items[0]; | ||
| </code> | </code> | ||
| - | </details> | ||
| - | Второй элемент — это цикл: | ||
| + | </details> Второй элемент — это цикл: | ||
| <code javascript> | <code javascript> | ||
| Строка 641: | Строка 631: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 649: | Строка 638: | ||
| minimum = items[i] | minimum = items[i] | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| - | <code php> | + | <code php> |
| <?php | <?php | ||
| Строка 663: | Строка 652: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 675: | Строка 664: | ||
| } | } | ||
| </code> | </code> | ||
| - | </details> | ||
| - | Если в массиве 10 элементов, цикл выполнится 9 раз, если 100 элементов — 99 раз, если n элементов, цикл выполнится //n-1// раз. В итоге, для массива из n элементов функция выполнит n операций — одну операцию инициализации и //n-1// операций в цикле. Если увеличить размер массива в 10 раз, то количество элементов будет равно 10*n, и количество операций также будет равно 10*n, то есть тоже вырастет в 10 раз. | ||
| - | Такая линейная временная сложность обозначается O(n). Из-за того, что в записи используется большая буква O, она называется «нотация О-большое». Буква O появилась здесь не случайно. Это первая буква немецкого слова **//Ordnung//**, которое означает порядок. В математике, откуда пришло обозначение, оно относится к порядку роста функций. | + | </details> Если в массиве 10 элементов, цикл выполнится 9 раз, если 100 элементов — 99 раз, если n элементов, цикл выполнится //n-1// раз. В итоге, для массива из n элементов функция выполнит n операций — одну операцию инициализации и //n-1// операций в цикле. Если увеличить размер массива в 10 раз, то количество элементов будет равно 10*n, и количество операций также будет равно 10*n, то есть тоже вырастет в 10 раз. |
| + | |||
| + | Такая линейная временная сложность обозначается O(n). Из-за того, что в записи используется большая буква O, она называется «нотация О-большое». Буква O появилась здесь не случайно. Это первая буква немецкого слова **//Ordnung//** , которое означает порядок. В математике, откуда пришло обозначение, оно относится к порядку роста функций. | ||
| Какие еще алгоритмы имеют линейную временную сложность? Например, алгоритм вычисления среднего арифметического: | Какие еще алгоритмы имеют линейную временную сложность? Например, алгоритм вычисления среднего арифметического: | ||
| Строка 694: | Строка 683: | ||
| </code> | </code> | ||
| - | + | <details> <summary>Python</summary> | |
| - | <details> | + | |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 707: | Строка 694: | ||
| return sum / len(items) | return sum / len(items) | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 726: | Строка 713: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 744: | Строка 731: | ||
| } | } | ||
| </code> | </code> | ||
| - | </details> | ||
| + | </details> | ||
| - | Анализ алгоритма показывает, что для массива из элементов будет n+1 операция: одна инициализация плюс n операций в цикле. Кажется, что такая временная сложность должна записываться O(n+1). Однако такие варианты, как n-2, n+5 и даже n+1000, всегда записывают как O(n). На первый взгляд это кажется странным, но далее мы разберемся, почему это так. А пока рассмотрим еще один линейный алгоритм — алгоритм определения строк-палиндромов. | + | Анализ алгоритма показывает, что для массива из элементов будет n+1 операция: одна инициализация плюс n операций в цикле. Кажется, что такая временная сложность должна записываться O(n+1). Однако такие варианты, как n-2, n+5 и даже n+1000, всегда записывают как O(n). На первый взгляд это кажется странным, но далее мы разберемся, почему это так. А пока рассмотрим еще один линейный алгоритм — алгоритм определения строк-палиндромов. |
| Палиндромом называется строка, которая одинаково читается слева направо и справа налево. АНА и ABBA — это палиндромы, а YES и NO — нет: | Палиндромом называется строка, которая одинаково читается слева направо и справа налево. АНА и ABBA — это палиндромы, а YES и NO — нет: | ||
| Строка 769: | Строка 756: | ||
| </code> | </code> | ||
| - | + | <details> <summary>Python</summary> | |
| - | <details> | + | |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 786: | Строка 771: | ||
| palindrome('abba') // true | palindrome('abba') // true | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 810: | Строка 795: | ||
| palindrome('abba') // true | palindrome('abba') // true | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| - | <code java> | + | <code java> |
| public class App { | public class App { | ||
| public static boolean palindrome(String word) { | public static boolean palindrome(String word) { | ||
| Строка 834: | Строка 819: | ||
| App.palindrome("abba") // true | App.palindrome("abba") // true | ||
| </code> | </code> | ||
| - | </details> | + | |
| - | В этом алгоритме цикл выполняется n/2 раз, где n — длина строки. Казалось бы, сложность работы алгоритма должна быть равна O(n/2). Но, как и в прошлый раз, это не так. Алгоритмы со временем работы 2n, 10n, n/5 и n/32 — все имеют сложность O(n), и снова это кажется странным. | + | </details> В этом алгоритме цикл выполняется n/2 раз, где n — длина строки. Казалось бы, сложность работы алгоритма должна быть равна O(n/2). Но, как и в прошлый раз, это не так. Алгоритмы со временем работы 2n, 10n, n/5 и n/32 — все имеют сложность O(n), и снова это кажется странным. |
| ===== Квадратичная сложность ===== | ===== Квадратичная сложность ===== | ||
| Строка 851: | Строка 836: | ||
| </code> | </code> | ||
| - | + | <details> <summary>Python</summary> | |
| - | <details> | + | |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 861: | Строка 844: | ||
| # ... | # ... | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 877: | Строка 860: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 891: | Строка 874: | ||
| } | } | ||
| </code> | </code> | ||
| - | </details> | ||
| - | Чтобы избавиться от несущественных деталей, в коде выше убрана часть операций — вместо них пустые комментарии. Попробуем оценить количество выполнений цикла. На первом шаге внешнего цикла внутренний выполнится //n-1// раз, на втором //n-2// раз, на третьем //n-3// и так далее: | ||
| - | {{ :basics_of_algorithms:eqweqweqwewq.png |}} | + | </details> Чтобы избавиться от несущественных деталей, в коде выше убрана часть операций — вместо них пустые комментарии. Попробуем оценить количество выполнений цикла. На первом шаге внешнего цикла внутренний выполнится //n-1// раз, на втором //n-2// раз, на третьем //n-3// и так далее: |
| - | Для расчетов мы взяли формулу суммы членов арифметической прогрессии. Среди слагаемых есть n<sup>2</sup>, так что речь идет о квадратичной сложности, которая записывается как O(n<sup>2</sup>). И снова встает вопрос: почему мы игнорируем деление на 2 и слагаемое //-3n+2//? Настало время разобраться. | + | {{ :basics_of_algorithms:eqweqweqwewq.png }} |
| + | |||
| + | Для расчетов мы взяли формулу суммы членов арифметической прогрессии. Среди слагаемых есть n<sup>2</sup> , так что речь идет о квадратичной сложности, которая записывается как O(n<sup>2</sup> ). И снова встает вопрос: почему мы игнорируем деление на 2 и слагаемое //-3n+2//? Настало время разобраться. | ||
| Как мы уже говорили, алгоритмическая сложность позволяет сравнивать алгоритмы «в целом». Можно утверждать, что все линейные алгоритмы в целом быстрее всех квадратичных, хотя на конкретных данных возможны аномалии. Все квадратичные алгоритмы в целом быстрее всех кубических. | Как мы уже говорили, алгоритмическая сложность позволяет сравнивать алгоритмы «в целом». Можно утверждать, что все линейные алгоритмы в целом быстрее всех квадратичных, хотя на конкретных данных возможны аномалии. Все квадратичные алгоритмы в целом быстрее всех кубических. | ||
| Строка 904: | Строка 887: | ||
| Но как только речь заходит о конкретике, выясняется, что операция сложения может быть очень быстрой, а операция деления — очень медленной по сравнению со сложением. Иногда четыре сложения могут выполниться быстрее, чем два деления. Поэтому нельзя в общем случае утверждать, что O(2n-3) быстрее, чем O(4n+1). | Но как только речь заходит о конкретике, выясняется, что операция сложения может быть очень быстрой, а операция деления — очень медленной по сравнению со сложением. Иногда четыре сложения могут выполниться быстрее, чем два деления. Поэтому нельзя в общем случае утверждать, что O(2n-3) быстрее, чем O(4n+1). | ||
| - | Именно поэтому программисты и математики избавляются от деталей в нотации O-большое. Записи вида O(2n-3), O(n<sup>2</sup>/3 + 5) и O(20n<sup>4</sup>-1000) превращаются в O(n), O(n<sup>2</sup>) и O(n<sup>4</sup>) соответственно. | + | Именно поэтому программисты и математики избавляются от деталей в нотации O-большое. Записи вида O(2n-3), O(n<sup>2</sup> /3 + 5) и O(20n<sup>4</sup> -1000) превращаются в O(n), O(n<sup>2</sup> ) и O(n<sup>4</sup> ) соответственно. |
| ===== Какая еще бывает сложность ===== | ===== Какая еще бывает сложность ===== | ||
| Строка 920: | Строка 903: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 927: | Строка 909: | ||
| return sorted_items[0] | return sorted_items[0] | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 940: | Строка 922: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 952: | Строка 934: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| Строка 958: | Строка 941: | ||
| ==== Логарифмическая сложность ==== | ==== Логарифмическая сложность ==== | ||
| - | Обозначается . За логарифмическое время работает алгоритм бинарного поиска. Эти алгоритмы относятся к быстрым, поскольку логарифмическая функция растет достаточно медленно. | + | Обозначается . За логарифмическое время работает алгоритм бинарного поиска. Эти алгоритмы относятся к быстрым, поскольку логарифмическая функция растет достаточно медленно. |
| - | {{ :basics_of_algorithms:image_processing20231003-35-rqiitr.png |}} | + | {{ :basics_of_algorithms:image_processing20231003-35-rqiitr.png }} |
| В массиве из тысячи элементов бинарный поиск работает максимум за десять сравнений, а массиве из миллиона — максимум за двадцать. Обычный метод перебора имеет линейную сложность, и поэтому будет работать за тысячу и миллион сравнений соответственно: | В массиве из тысячи элементов бинарный поиск работает максимум за десять сравнений, а массиве из миллиона — максимум за двадцать. Обычный метод перебора имеет линейную сложность, и поэтому будет работать за тысячу и миллион сравнений соответственно: | ||
| - | | n | O(log*n) | O(n) | | + | |n|O(log*n)|O(n)| |
| - | | 1000 | 10 | 1000 | | + | |1000|10|1000| |
| - | | 1000000 | 20 | 1000000 | | + | |1000000|20|1000000| |
| Логарифмические алгоритмы считаются очень быстрыми, гораздо быстрее линейных. | Логарифмические алгоритмы считаются очень быстрыми, гораздо быстрее линейных. | ||
| Строка 974: | Строка 957: | ||
| Она обозначается как O(nlogn) и описывает сложность алгоритма быстрой сортировки. Сравним количество операций у быстрой сортировки и сортировки выбором — так мы увидим, почему быстрая сортировка так называется: | Она обозначается как O(nlogn) и описывает сложность алгоритма быстрой сортировки. Сравним количество операций у быстрой сортировки и сортировки выбором — так мы увидим, почему быстрая сортировка так называется: | ||
| - | | | Быстрая O(n*logn) | Выбор O(n<sup>2</sup>) | | + | | |Быстрая O(n*logn) |Выбор O(n<sup>2</sup> )| |
| - | | 1000 | 10000 | 1000000 | | + | |1000|10000|1000000| |
| - | | 1000000 | 20000000 | 1000000000000 | | + | |1000000|20000000|1000000000000| |
| Быстрая сортировка упорядочивает массив из тысячи элементов приблизительно за десять тысяч операций, в то время как сортировка выбором — за миллион. Время выполнения различается в сто раз, и с ростом n разница только растет! Но важно не забывать, что на очень маленьких массивах (из десяти элементов) сортировка выбором может оказаться быстрее. Так происходит потому, что алгоритм сортировки выбором проще. Быстрая сортировка сложнее, и накладные расходы в реализации оказываются слишком велики для небольшого набора данных. | Быстрая сортировка упорядочивает массив из тысячи элементов приблизительно за десять тысяч операций, в то время как сортировка выбором — за миллион. Время выполнения различается в сто раз, и с ростом n разница только растет! Но важно не забывать, что на очень маленьких массивах (из десяти элементов) сортировка выбором может оказаться быстрее. Так происходит потому, что алгоритм сортировки выбором проще. Быстрая сортировка сложнее, и накладные расходы в реализации оказываются слишком велики для небольшого набора данных. | ||
| Строка 984: | Строка 967: | ||
| ==== Экспоненциальная сложность ==== | ==== Экспоненциальная сложность ==== | ||
| - | Сколько подмассивов можно получить из массива ? Попробуем выяснить, но сначала определимся с условиями: | + | Сколько подмассивов можно получить из массива ? Попробуем выяснить, но сначала определимся с условиями: |
| - | * Подмассивы могут быть любой длины, включая ноль | + | * Подмассивы могут быть любой длины, включая ноль |
| - | * Будем считать одним подмассивом все подмассивы, состоящие из одних и тех же элементов в разном порядке (например, и ) | + | * Будем считать одним подмассивом все подмассивы, состоящие из одних и тех же элементов в разном порядке (например, и ) |
| Выпишем все варианты и посчитаем их: | Выпишем все варианты и посчитаем их: | ||
| - | | %%[]%% | %%[4]%% | %%[2,3]%% | %%[1,2,4]%% | | + | |<nowiki>[]</nowiki>|<nowiki>[4]</nowiki>|<nowiki>[2,3]</nowiki>|<nowiki>[1,2,4]</nowiki>| |
| - | | %%[1]%% | %%[1,2]%% | %%[2,4]%% | %%[1,3,4]%% | | + | |<nowiki>[1]</nowiki>|<nowiki>[1,2]</nowiki>|<nowiki>[2,4]</nowiki>|<nowiki>[1,3,4]</nowiki>| |
| - | | %%[2]%% | %%[1,3]%% | %%[3,4]%% | %%[2,3,4]%% | | + | |<nowiki>[2]</nowiki>|<nowiki>[1,3]</nowiki>|<nowiki>[3,4]</nowiki>|<nowiki>[2,3,4]</nowiki>| |
| - | | %%[3]%% | %%[1,4]%% | %%[1,2,3]%% | %%[1,2,3,4]%% | | + | |<nowiki>[3]</nowiki>|<nowiki>[1,4]</nowiki>|<nowiki>[1,2,3]</nowiki>|<nowiki>[1,2,3,4]</nowiki>| |
| - | Всего 16. Существует общее правило, по которому возможное количество подмассивов у массива длины n составляет 2<sup>n</sup>. Формулы вида 2<sup>n</sup>, 3<sup>n</sup>, 100<sup>n</sup> называют **экспонентами**. Алгоритм, который может построить список всех подмассивов массива длины n, имеет экспоненциальную сложность O(2<sup>n</sup>). | + | Всего 16. Существует общее правило, по которому возможное количество подмассивов у массива длины n составляет 2<sup>n</sup> . Формулы вида 2<sup>n</sup> , 3<sup>n</sup> , 100<sup>n</sup> называют **экспонентами**. Алгоритм, который может построить список всех подмассивов массива длины n, имеет экспоненциальную сложность O(2<sup>n</sup> ). |
| Алгоритмы экспоненциальной сложности считаются медленными. Количество подмассивов у массива из тридцати элементов равно 1073741824, то есть превышает миллиард! | Алгоритмы экспоненциальной сложности считаются медленными. Количество подмассивов у массива из тридцати элементов равно 1073741824, то есть превышает миллиард! | ||
| Строка 1002: | Строка 985: | ||
| ==== Факториальная сложность ==== | ==== Факториальная сложность ==== | ||
| - | Обозначается O(n!). Факториалом числа называют произведение 1x2x...xX1, то есть всех чисел от 1 до n. Сложность алгоритма, который находит все перестановки массива, равна O(n!). Вот все перестановки массива %%[1,2,3,4]%%: | + | Обозначается O(n!). Факториалом числа называют произведение 1x2x…xX1, то есть всех чисел от 1 до n. Сложность алгоритма, который находит все перестановки массива, равна O(n!). Вот все перестановки массива <nowiki>[1,2,3,4]</nowiki>: |
| - | | %%[1,2,3,4]%% | %%[2,1,3,4]%% | %%[3,2,1,4]%% | %%[4,2,3,1]%% | | + | |<nowiki>[1,2,3,4]</nowiki>|<nowiki>[2,1,3,4]</nowiki>|<nowiki>[3,2,1,4]</nowiki>|<nowiki>[4,2,3,1]</nowiki>| |
| - | | %%[1,2,4,3]%% | %%[2,1,3,3]%% | %%[3,2,4,1]%% | %%[4,2,1,3]%% | | + | |<nowiki>[1,2,4,3]</nowiki>|<nowiki>[2,1,3,3]</nowiki>|<nowiki>[3,2,4,1]</nowiki>|<nowiki>[4,2,1,3]</nowiki>| |
| - | | %%[1,3,2,4]%% | %%[2,3,1,4]%% | %%[3,1,2,4]%% | %%[4,3,2,1]%% | | + | |<nowiki>[1,3,2,4]</nowiki>|<nowiki>[2,3,1,4]</nowiki>|<nowiki>[3,1,2,4]</nowiki>|<nowiki>[4,3,2,1]</nowiki>| |
| - | | %%[1,3,4,2]%% | %%[2,3,4,1]%% | %%[3,1,4,2]%% | %%[4,3,1,2]%% | | + | |<nowiki>[1,3,4,2]</nowiki>|<nowiki>[2,3,4,1]</nowiki>|<nowiki>[3,1,4,2]</nowiki>|<nowiki>[4,3,1,2]</nowiki>| |
| - | | %%[1,4,2,3]%% | %%[2,4,1,3]%% | %%[3,4,2,1]%% | %%[4,1,2,3]%% | | + | |<nowiki>[1,4,2,3]</nowiki>|<nowiki>[2,4,1,3]</nowiki>|<nowiki>[3,4,2,1]</nowiki>|<nowiki>[4,1,2,3]</nowiki>| |
| - | | %%[1,4,3,2]%% | %%[2,4,3,1]%% | %%[3,4,1,3]%% | %%[4,1,3,2]%% | | + | |<nowiki>[1,4,3,2]</nowiki>|<nowiki>[2,4,3,1]</nowiki>|<nowiki>[3,4,1,3]</nowiki>|<nowiki>[4,1,3,2]</nowiki>| |
| - | Всего их 4!=24. Факториальная сложность самая медленная из тех, что мы рассмотрели. Если нам потребуется найти все перестановки массива из тридцати элементов, их окажется 265252859812191058636308480000000, то есть 268 миллионов миллионов миллионов миллионов миллионов. Даже на самом быстром современном компьютере поиск всех перестановок займет миллионы миллионов лет. | + | Всего их 4!=24. Факториальная сложность самая медленная из тех, что мы рассмотрели. Если нам потребуется найти все перестановки массива из тридцати элементов, их окажется 265252859812191058636308480000000, то есть 268 миллионов миллионов миллионов миллионов миллионов. Даже на самом быстром современном компьютере поиск всех перестановок займет миллионы миллионов лет. |
| ===== Сводная таблица временной сложности ===== | ===== Сводная таблица временной сложности ===== | ||
| - | | **Название** | **Формула** | **Примеры алгоритмов** | | + | |**Название** |**Формула** |**Примеры алгоритмов** | |
| - | | Константная | o(1) | Длина массива | | + | |Константная|o(1)|Длина массива| |
| - | | Логарифмическая | O(logn) | Бинарный поиск | | + | |Логарифмическая|O(logn)|Бинарный поиск| |
| - | | Линейная | O(n) | Поиск методом перебора | | + | |Линейная|O(n)|Поиск методом перебора| |
| - | | Линейно-логарифмическая | O(nlogn) | Быстрая сортировка | | + | |Линейно-логарифмическая|O(nlogn)|Быстрая сортировка| |
| - | | Квадратичная | O(n<sup>2</sup>) | Сортировка выбором, пузырьковая сортировка | | + | |Квадратичная|O(n<sup>2</sup> )|Сортировка выбором, пузырьковая сортировка| |
| - | | Экспоненциальная | O(2<sup>n</sup>) | Список подмассивов | | + | |Экспоненциальная|O(2<sup>n</sup> )|Список подмассивов| |
| - | | Факториальная | O(n!) | Список перестановок | | + | |Факториальная|O(n!)|Список перестановок| |
| - | Иногда в литературе можно встретить название **полиномиальные алгоритмы** — к ним относят алгоритмы со сложностью O(n<sup>2</sup>), O(n<sup>3</sup>) или O(n<sup>100</sup>). Условная граница между медленными и быстрыми алгоритмами проходит между **полиномиальными** и **экспоненциальными алгоритмами**. | + | Иногда в литературе можно встретить название **полиномиальные алгоритмы** — к ним относят алгоритмы со сложностью O(n<sup>2</sup> ), O(n<sup>3</sup> ) или O(n<sup>100</sup> ). Условная граница между медленными и быстрыми алгоритмами проходит между **полиномиальными** и **экспоненциальными алгоритмами**. |
| ==== Оценка памяти ==== | ==== Оценка памяти ==== | ||
| Строка 1048: | Строка 1031: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 1063: | Строка 1045: | ||
| i += 1 | i += 1 | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>PHP</summary> |
| - | <summary>PHP</summary> | + | |
| <code php> | <code php> | ||
| Строка 1086: | Строка 1068: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| </details> | </details> | ||
| - | <details> | + | <details> <summary>Java</summary> |
| - | <summary>Java</summary> | + | |
| <code java> | <code java> | ||
| Строка 1105: | Строка 1087: | ||
| } | } | ||
| </code> | </code> | ||
| - | </details> | + | |
| - | Этих неповторяющихся элементов будет чуть меньше, чем элементов в исходном массиве. Но при этом размер множества будет соизмерим с размером массива, поэтому речь идет о линейной сложности по памяти. | + | </details> Этих неповторяющихся элементов будет чуть меньше, чем элементов в исходном массиве. Но при этом размер множества будет соизмерим с размером массива, поэтому речь идет о линейной сложности по памяти. |
| ===== Оптимизация ===== | ===== Оптимизация ===== | ||
| Строка 1120: | Строка 1102: | ||
| Для определения простоты числа можно использовать один из самых древних, известных человечеству, алгоритмов — **Решето Эратосфена**. Сначала мы записываем список чисел, начиная с двойки: | Для определения простоты числа можно использовать один из самых древних, известных человечеству, алгоритмов — **Решето Эратосфена**. Сначала мы записываем список чисел, начиная с двойки: | ||
| - | | 2 | 3 | 4 | 5 | 6 | | + | |2|3|4|5|6| |
| - | | 7 | 8 | 9 | 10 | 11 | | + | |7|8|9|10|11| |
| - | | 12 | 13 | 14 | 15 | 16 | | + | |12|13|14|15|16| |
| - | | 17 | 18 | 19 | 20 | 21 | | + | |17|18|19|20|21| |
| - | | 22 | 23 | 24 | 25 | 26 | | + | |22|23|24|25|26| |
| Берем первое число — двойку. Выделяем цветом числа, которые делятся на нее. Саму двойку не выделяем: | Берем первое число — двойку. Выделяем цветом числа, которые делятся на нее. Саму двойку не выделяем: | ||
| - | | 2 | 3 | <color green>4</color> | 5 | ''6'' | | + | |2|3|<color /#fff3cd>4</color>|5|<color /#fff3cd>6</color>| |
| - | | 7 | ''8'' | 9 | ''10'' | 11 | | + | |7|<color /#fff3cd>8</color>|9|<color /#fff3cd>10</color>|11| |
| - | | 12 | 13 | 14 | 15 | 16 | | + | |<color /#fff3cd>12</color>|13|<color /#fff3cd>14</color>|15|<color /#fff3cd>16</color>| |
| - | | 17 | 18 | 19 | 20 | 21 | | + | |17|<color /#fff3cd>18</color>|19|<color /#fff3cd>20</color>|21| |
| - | | 22 | 23 | 24 | 25 | 26 | | + | |<color /#fff3cd>22</color>|23|<color /#fff3cd>24</color>|25|<color /#fff3cd>26</color>| |
| Следующее неотмеченное число — три. Выделяем цветом числа, которые делятся на три, но не саму тройку: | Следующее неотмеченное число — три. Выделяем цветом числа, которые делятся на три, но не саму тройку: | ||
| - | | 2 | 3 | 4 | 5 | 6 | | + | |2|3|<color /#fff3cd>4</color>|5|<color /#fff3cd>6</color>| |
| - | | 7 | 8 | 9 | 10 | 11 | | + | |7|<color /#fff3cd>8</color>|<color /#fff3cd>9</color>|<color /#fff3cd>10</color>|11| |
| - | | 12 | 13 | 14 | 15 | 16 | | + | |<color /#fff3cd>12</color>|13|<color /#fff3cd>14</color>|<color /#fff3cd>15</color>|<color /#fff3cd>16</color>| |
| - | | 17 | 18 | 19 | 20 | 21 | | + | |17|<color /#fff3cd>18</color>|19|<color /#fff3cd>20</color>|<color /#fff3cd>21</color>| |
| - | | 22 | 23 | 24 | 25 | 26 | | + | |<color /#fff3cd>22</color>|23|<color /#fff3cd>24</color>|25|<color /#fff3cd>26</color>| |
| Четверка зачеркнута — она делится на два, поэтому мы ее пропускаем. | Четверка зачеркнута — она делится на два, поэтому мы ее пропускаем. | ||
| - | Переходим к пятерке. У нас уже отмечены числа 10, 20 (оба делятся на два) и 15 (делится на три). Единственное неотмеченное число — это 25. Это подсказка, которая помогает понять одну важную мысль — чтобы составить список простых чисел вплоть до , достаточно повторить эту процедуру только для чисел от до . | + | Переходим к пятерке. У нас уже отмечены числа 10, 20 (оба делятся на два) и 15 (делится на три). Единственное неотмеченное число — это 25. Это подсказка, которая помогает понять одну важную мысль — чтобы составить список простых чисел вплоть до N, достаточно повторить эту процедуру только для чисел от 2 до √N. |
| - | Сама процедура выделения чисел на каждой итерации пробегает чисел. Итого, выходит чисел на итерацию и итераций. Сложность алгоритма по времени равна или в более математической записи — . При этом нам приходится выделять память для всех чисел, поэтому сложность по памяти равна . | + | Сама процедура выделения чисел на каждой итерации пробегает N чисел. Итого, выходит N чисел на итерацию и √N итераций. Сложность алгоритма по времени равна O(N x √N) или в более математической записи — O(N<sup>3/2</sup> ). При этом нам приходится выделять память для всех N чисел, поэтому сложность по памяти равна O(N). |
| Решето Эратосфена — сложный алгоритм, как по времени, так и по памяти. | Решето Эратосфена — сложный алгоритм, как по времени, так и по памяти. | ||
| - | Чтобы оптимизировать решение, мы должны найти или придумать другой алгоритм. Обратим внимание, что Решето строит список простых чисел от до , но нам нужно только последнее число . Мы можем проверить, что число не делится ни на какие целые числа от до : | + | Чтобы оптимизировать решение, мы должны найти или придумать другой алгоритм. Обратим внимание, что Решето строит список простых чисел от 2 до N, но нам нужно только последнее число N. Мы можем проверить, что число не делится ни на какие целые числа от 2 до N-1: |
| <code javascript> | <code javascript> | ||
| Строка 1164: | Строка 1146: | ||
| </code> | </code> | ||
| - | <details> | + | <details> <summary>Python</summary> |
| - | <summary>Python</summary> | + | |
| <code python> | <code python> | ||
| Строка 1174: | Строка 1155: | ||
| return True | return True | ||
| </code> | </code> | ||
| - | </detais> | ||
| - | <details> | + | </details> |
| - | <summary>Java</summary> | + | |
| + | <details> <summary>Java</summary> | ||
| <code java> | <code java> | ||
| Строка 1192: | Строка 1173: | ||
| } | } | ||
| </code> | </code> | ||
| - | </details> | ||
| - | Этот алгоритм линейный по времени, он работает за . Он константный по памяти, , поскольку количество потребляемой памяти не зависит от . | ||
| - | Он работает гораздо быстрее Решета, но все еще не самый оптимальный. Как мы помним, для проверки нам не обязательно делить на все числа меньше себя, достаточно проверить только числа от до , так что алгоритм можно переписать. | + | </details> Этот алгоритм линейный по времени, он работает за O(N). Он константный по памяти, O(1), поскольку количество потребляемой памяти не зависит от N. |
| - | Алгоритмическая сложность переписанного алгоритма равна или . | + | Он работает гораздо быстрее Решета, но все еще не самый оптимальный. Как мы помним, для проверки нам не обязательно делить N на все числа меньше себя, достаточно проверить только числа от 2 до √N, так что алгоритм можно переписать. |
| + | |||
| + | Алгоритмическая сложность переписанного алгоритма равна O(√N) или O(N<sup>1/2</sup> ). | ||
| ===== Выводы ===== | ===== Выводы ===== | ||
| - | - При общих равных условиях программисты выбирают самые быстрые и самые экономичные алгоритмы | + | - При общих равных условиях программисты выбирают самые быстрые и самые экономичные алгоритмы |
| - | - Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных | + | - Выбрать самый быстрый алгоритм оказывается не так просто. Измерения на конкретных данных не позволяют прогнозировать время и память алгоритмов на других данных |
| + | - Программисты используют нотацию О-большое, чтобы оценить производительность алгоритмов в целом | ||
| + | - Чаще всего встречаются такие сложности, как константная, логарифмическая, линейная, линейно-логарифмическая, квадратическая, экспоненциальная и факториальная. В этом списке они распределены в порядке от самой быстрой к самой медленной | ||
| + | - Нотация О-большое оценивает не только скорость алгоритма, но и память, которую он использует | ||
| + | ===== Примеры ===== | ||
| + | Реализуйте функцию, которая проверяет являться ли число простым или нет. | ||
| + | |||
| + | Оптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций | ||
| + | |||
| + | **solutions/solution.js** | ||
| + | Реализуйте и экспортируйте функцию по умолчанию | ||
| + | <code javascript> | ||
| + | import isPrime from './solution.js'; | ||
| + | |||
| + | isPrime(2147483648) // false | ||
| + | isPrime(87178291199) // true | ||
| + | </code> | ||
| + | |||
| + | **Решение:** | ||
| + | <code javascript> | ||
| + | const isPrime = (number) => { | ||
| + | if (number < 2) { | ||
| + | return false; | ||
| + | } | ||
| + | |||
| + | const sqrt = Math.sqrt(number); | ||
| + | for (let i = 2; i <= sqrt; i += 1) { | ||
| + | if (number % i === 0) { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | return true; | ||
| + | }; | ||
| + | |||
| + | export default isPrime; | ||
| + | </code> | ||
| + | |||
| + | |||
| + | <details> | ||
| + | <summary>**solutions/solution.php**</summary> | ||
| + | Реализуйте функцию <color red>solution</color>. | ||
| + | <code php> | ||
| + | <?php | ||
| + | |||
| + | solution(2147483648) # False | ||
| + | solution(87178291199) # True | ||
| + | </code> | ||
| + | **Решение:** | ||
| + | <code php> | ||
| + | <?php | ||
| + | |||
| + | function solution(int $num): bool | ||
| + | { | ||
| + | if ($num < 2) { | ||
| + | return false; | ||
| + | } | ||
| + | |||
| + | for ($i = 2; $i <= sqrt($num); $i += 1) { | ||
| + | if ($num % $i == 0) { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | return true; | ||
| + | } | ||
| + | </code> | ||
| + | </details> | ||
| + | |||
| + | |||
| + | |||
| + | <details> | ||
| + | |||
| + | <summary>**solutions/solution.py**</summary> | ||
| + | Реализуйте функцию solution. | ||
| + | <code python> | ||
| + | from solution import solution | ||
| + | |||
| + | solution(2147483648) # False | ||
| + | solution(87178291199) # True | ||
| + | </code> | ||
| + | **Решение:** | ||
| + | <code python> | ||
| + | import math | ||
| + | |||
| + | |||
| + | def solution(number): | ||
| + | if number < 2: | ||
| + | return False | ||
| + | |||
| + | sqrt = math.sqrt(number) | ||
| + | for i in range(2, int(sqrt)): | ||
| + | if number % i == 0: | ||
| + | return False | ||
| + | |||
| + | return True | ||
| + | </code> | ||
| + | </details> | ||
| + | |||
| + | |||
| + | <details> | ||
| + | <summary>**solutions/Solution.java**</summary> | ||
| + | В файле определите пакет <color red>solutions</color>. Создайте в нем публичный класс Solution и реализуйте в нем публичный статический метод <color red>run()</color>. Метод принимает в качестве параметра целое число типа <color red>long</color> и проверяет, является ли оно простым или нет | ||
| + | <code java> | ||
| + | Solution.run(2147483648); // false | ||
| + | Solution.run(87178291199); // true | ||
| + | </code> | ||
| + | Оптимизируйте алгоритм так, чтобы он выполнялся за наименьшее количество итераций | ||
| + | **Решение:** | ||
| + | <code java> | ||
| + | package solutions; | ||
| + | |||
| + | public class Solution { | ||
| + | public static boolean run(long number) { | ||
| + | if (number < 2) { | ||
| + | return false; | ||
| + | } | ||
| + | |||
| + | var sqrt = Math.sqrt(number); | ||
| + | |||
| + | for (var i = 2; i <= sqrt; i++) { | ||
| + | if (number % i == 0) { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | return true; | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| + | </details> | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
basics_of_algorithms/algorithmic_complexity.1696419844.txt.gz · Последние изменения: 2023/10/04 14:44 — werwolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Share Alike 4.0 International
