Примеры алгоритмов, которые имеют O (1), O (n log n) и O (log n) сложности

Ответ 1

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

O (1) время
1. Доступ к индексу массива (int a = ARR [5];)
2. Вставка node в Связанный список
3. Нажатие и наложение на стек
4. Вставка и удаление из очереди
5. Выясните родительский или левый/правый дочерний элемент node в дереве, хранящемся в Array
6. Переход к следующему/предыдущему элементу в двойном связанном списке
и вы можете найти еще миллион таких примеров...

O (n) время
1. Перемещение массива
2. Перемещение связанного списка
3. Линейный поиск
4. Удаление определенного элемента в связанном списке (не отсортировано)
5. Сравнение двух строк
6. Проверка на Palindrome
7. Подсчет/сортировка ковша
и здесь тоже вы можете найти еще миллион таких примеров....
В двух словах, все алгоритмы Brute Force или Noob, которые требуют линейности, основаны на временной сложности O (n)

O (log n) время
1. Двоичный поиск
2. Поиск наибольшего/наименьшего числа в двоичном дереве поиска
3. Определенные алгоритмы Divide и Conquer, основанные на линейной функциональности
4. Вычисление чисел Фибоначчи - лучший метод
Основная предпосылка здесь НЕ использует полные данные и уменьшает размер проблемы с каждой итерацией

O (nlogn) время
1. Слияние Сортировка
2. Куча Сортировка
3. Быстрая сортировка
4. Определенные алгоритмы Divide и Conquer, основанные на оптимизации алгоритмов O (n ^ 2)
Коэффициент "log n" вводится с учетом Divide и Conquer. Некоторые из этих алгоритмов являются лучшими оптимизированными и часто используются.

O (n ^ 2) время
1. Bubble Sort
2. Вставка Сортировка
3. Выбор Сортировка
4. Прохождение простого 2D-массива
Предполагается, что они являются менее эффективными алгоритмами, если их O (nlogn) -матрицы присутствуют. Общее приложение может быть здесь Brute Force.

Надеюсь, это хорошо ответит на ваш вопрос. Если у пользователей есть больше примеров для добавления, я буду более чем счастлив:)

Ответ 2

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

Типичным примером O(N log N) будет сортировка входного массива с хорошим алгоритмом (например, mergesort).

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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


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

Ответ 8

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

Ответ 9

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

O(1) - определение того, является ли число четным или нечетным; Работа с HashMap

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

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