Оценка сложности алгоритмов |
|||||||
МЕНЮ Искусственный интеллект Поиск Регистрация на сайте Помощь проекту ТЕМЫ Новости ИИ Искусственный интеллект Разработка ИИГолосовой помощник Городские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Техническое зрение Чат-боты Авторизация |
2020-03-10 05:04 O(1) — константная сложность Это время работы алгоритма, которое не зависит от входных данных. Например: простые арифметические операции, определение чётности целого числа (представленного в двоичном виде) и так далее. O(n) — линейная сложность Поиск наименьшего или наибольшего элемента в неотсортированном массиве, один проход по списку/массиву/словарю, зависит непосредственно от количества элементов. O(log n) — логарифмическая сложность Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов. (Под понятием log n обычно имеется в виду логарифм n по основанию 2, однако обычно основание опускается). O(n?) — квадратичная сложность Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n*n, т. е. n?. Грубо говоря, квадратичную сложность имеет цикл с вложенным циклом. O(n?) — кубическая сложность Такую сложность имеет обычное умножение двух n*n матриц. ОЧЕНЬ грубо говоря это цикл, в который вложен цикл, в который вложен цикл. O(n!) — факториальная сложность Обычно такую сложность имеют задачи, в которых реализуется полный перебор. Зачастую, такая сложность имеет место быть при небольших входных данных. O(2^p(n)) — Экспоненциальная сложность p(n) — полиномиальная функция от n. Пример: перемножение матриц с помощью полного перебора. Это были основные типы сложности работы алгоритмов. Также существуют сложности, зависящие не от одного, а от нескольких независимых входных данных. Так мы можем получить сложность O(n*log n), если мы n раз проводим бинарный поиск или сложность O(n*m), если мы m раз проходим по массиву размером в n элементов. Также мы можем получить сложность O(n+m?), если, к примеру, мы пройдем по массиву один раз, проверив не отсортирован ли он, а затем отсортируем его с помощью алгоритма qsort. Что за qsort? Это quick sort, самый распространенный и простой алгоритм сортировки. Думаю, один из ближайших постов будет именно о нём. Как мы видим, алгоритмов сортировки великое множество, и у всех из них есть как свои преимущества, так и недостатки. Также возможна реализация сортировки за линейное время на ядрах CUDA у Nvidia, но лишь при небольшом кол-ве элементов. Также, если вы всерьёз займетесь программированием, вы найдете для себя любимый способ сортировки(а, может, и вовсе напишите свой, как студенты МФТИ). К слову, у админа любимый способ сортировки — сортировка подсчетом(Counting Sort). Существуют также сложности 2^n, 3^n и прочие, однако они не так распространены и малоэффективны. Постарайтесь не усложнять свой код до такой сложности по времени. Попробуйте написать решение к этой задаче и оценить сложность алгоритма, зная приведенную выше информацию: Вам известны два катета прямоугольного треугольника, найдите его гипотенузу и площадь. Используйте библиотеку math. Функция квадратного корня — math.sqrt() Источник: m.vk.com Комментарии: |
||||||