Какие алгоритмы, которые мы используем ежедневно, имеют сложность O (1), O (n log n) и O (log n)?

Если вам нужны примеры алгоритмов / группы операторов со сложностью времени, как указано в вопросе, вот небольшой список -

O(1) время

• Доступ к индексу массива (int a = ARR [5];)
• Вставка узла в связанный список
• Нажатие на стек
• Вставка и удаление из очереди
• Определение родителя или левого / правого дочернего элемента узла в дереве, хранящемся в массиве
• Переход к следующему / предыдущему элементу в двусвязном списке

O(n) время

Вкратце, все алгоритмы грубой силы или алгоритмы Noob, требующие линейности, основаны на временной сложности O (n).

• Обход массива
• Обход связанного списка
• Линейный поиск
• Удаление определенного элемента в связанном списке (не отсортировано)
• Сравнение двух строк
• Проверка на палиндром
• Counting / Bucket Sort, и здесь вы также можете найти еще миллион таких примеров ....

O(log n) время

• Бинарный поиск
• Поиск наибольшего / наименьшего числа в двоичном дереве поиска
• Определенные алгоритмы разделения и владения, основанные на линейной функциональности
• Вычисление чисел Фибоначчи - лучший метод Основная предпосылка здесь - НЕ использовать полные данные и уменьшать размер проблемы с каждой итерацией.

O(n log n) время

Фактор log n вводится с учетом принципа «Разделяй и властвуй». Некоторые из этих алгоритмов являются наиболее оптимизированными и часто используются.

• Сортировка слиянием
• Сортировка кучи
• Быстрая сортировка
• Некоторые алгоритмы «разделяй и властвуй», основанные на оптимизации алгоритмов O (n ^ 2)

O(n^2) время

Предполагается, что эти алгоритмы будут менее эффективными, если присутствуют их аналоги O (nlogn). Общее приложение может быть здесь грубой силой.

• Пузырьковая сортировка
• Сортировка вставкой
• Выбор Сортировка
• Обход простого 2D-массива

Простым примером O(1)может быть return 23;- независимо от ввода, он вернется через фиксированное конечное время.

Типичным примером O(N log N)является сортировка входного массива с помощью хорошего алгоритма (например, сортировка слиянием).

Типичный пример O(log N)поиска значения в отсортированном массиве ввода пополам.

O (1) - большинство процедур приготовления - это O (1), то есть на это требуется постоянное количество времени, даже если есть больше людей, для которых нужно готовить (до некоторой степени, потому что в кастрюле / сковороде может закончиться место и приготовление нужно разделить)

О (войти) - найти что-то в телефонной книге. Подумайте о двоичном поиске.

O (n) - чтение книги, где n - количество страниц. Это минимальное время, необходимое для чтения книги.

O (nlogn) - не могу сразу придумать что-то, что можно делать каждый день, кроме nlogn ... если только вы не отсортируете карты, выполнив слияние или быструю сортировку!

Могу предложить вам несколько общих алгоритмов ...

• O (1): доступ к элементу в массиве (например, int i = a [9])
• O (n log n): быстрая сортировка или сортировка слиянием (в среднем)
• O (log n): двоичный поиск

Это будут интуитивные ответы, поскольку это звучит как вопрос типа домашнего задания / собеседования. Если вы ищете что-то более конкретное, это немного сложнее, поскольку общественность в целом не будет иметь представления о базовой реализации (конечно, с сохранением открытого исходного кода) популярного приложения, и эта концепция в целом не применима к «приложению»

O (1): найти лучший следующий ход в шахматах (или го, если на то пошло). Поскольку количество состояний игры конечно, это всего лишь O (1) :-)

Сложность программного приложения не измеряется и не записывается в нотации с большой буквы. Полезно только измерять сложность алгоритма и сравнивать алгоритмы в одной и той же области. Скорее всего, когда мы говорим O (n), мы имеем в виду, что это «O (n) сравнений » или «O (n) арифметических операций». Это означает, что вы не можете сравнивать никакую пару алгоритмов или приложений.

O (1) - Удаление элемента из двусвязного списка. например

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}

Вы можете добавить в свой список следующие алгоритмы:

O(1)- Определение четного или нечетного числа; Работа с HashMap

O(logN) - вычисление x ^ N,

O(N Log N) - Самая длинная возрастающая подпоследовательность

O (n log n) - это известная верхняя граница того, насколько быстро вы можете отсортировать произвольный набор (при условии стандартной, а не высокопараллельной модели вычислений).

0 (logn) -Двоичный поиск, элемент пика в массиве (может быть более одного пика) 0 (1) -в Python вычисление длины списка или строки. Функция len () занимает 0 (1) раз. Доступ к элементу в массиве занимает 0 (1) раз. Операция отправки в стек занимает 0 (1) раз. 0 (nlogn) - Сортировка по слиянию. сортировка в python занимает nlogn времени. поэтому, когда вы используете listname.sort (), требуется время входа n.

Примечание. Поиск в хеш-таблице иногда занимает больше времени из-за коллизий.

O (2 ^N )

O (2 ^N ) обозначает алгоритм, рост которого удваивается с каждым добавлением к входному набору данных. Кривая роста функции O (2 ^N ) является экспоненциальной - сначала очень мелкой, а затем стремительно поднимающейся. Примером функции O (2 ^N ) является рекурсивное вычисление чисел Фибоначчи:

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}