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

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

91 голос | спросил Rachel 20 +04002009-10-20T09:33:17+04:00312009bEurope/MoscowTue, 20 Oct 2009 09:33:17 +0400 2009, 09:33:17

11 ответов


0

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

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

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

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

O (nlogn) время
1. Объединить сортировку
2. Сортировка кучи
3. Быстрая сортировка
4. Некоторые алгоритмы «разделяй и властвуй», основанные на оптимизации алгоритмов O (n ^ 2)
Фактор 'log n' вводится с учетом разделения и завоевания. Некоторые из этих алгоритмов являются наиболее оптимизированными и часто используются.

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

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

ответил Karan Bajaj 23 J000000Monday12 2012, 15:37:22
0

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

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

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

ответил Alex Martelli 20 +04002009-10-20T09:43:24+04:00312009bEurope/MoscowTue, 20 Oct 2009 09:43:24 +0400 2009, 09:43:24
0

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

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

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

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

ответил Chii 20 +04002009-10-20T09:57:25+04:00312009bEurope/MoscowTue, 20 Oct 2009 09:57:25 +0400 2009, 09:57:25
0

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

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

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

ответил Scanningcrew 20 +04002009-10-20T09:43:12+04:00312009bEurope/MoscowTue, 20 Oct 2009 09:43:12 +0400 2009, 09:43:12
0

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

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


void delete(node **head, node *to_delete)
{
    .
    .
    .
}
ответил sigjuice 20 +04002009-10-20T13:13:13+04:00312009bEurope/MoscowTue, 20 Oct 2009 13:13:13 +0400 2009, 13:13:13
0

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

ответил P Shved 20 +04002009-10-20T09:40:44+04:00312009bEurope/MoscowTue, 20 Oct 2009 09:40:44 +0400 2009, 09:40:44
0

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

ответил Carsten 20 +04002009-10-20T09:50:33+04:00312009bEurope/MoscowTue, 20 Oct 2009 09:50:33 +0400 2009, 09:50:33
0

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

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

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

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

ответил rachvela 20 +04002009-10-20T11:01:44+04:00312009bEurope/MoscowTue, 20 Oct 2009 11:01:44 +0400 2009, 11:01:44
0

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

ответил Carsten 20 +04002009-10-20T09:47:21+04:00312009bEurope/MoscowTue, 20 Oct 2009 09:47:21 +0400 2009, 09:47:21
0

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

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

ответил Abhinav Vajpeyi 17 +03002018-10-17T16:36:37+03:00312018bEurope/MoscowWed, 17 Oct 2018 16:36:37 +0300 2018, 16:36:37
0

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);
}
ответил Hefaz 29 +03002018-10-29T18:38:13+03:00312018bEurope/MoscowMon, 29 Oct 2018 18:38:13 +0300 2018, 18:38:13

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132