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

Question

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

• O (1): Доступ к элементу в массиве (т.е. Int я = а [9])
• O (п журнал п) : быстро или слияние (в среднем)
• O (журнал N): Двоичный поиск

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

Answer 8

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

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

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

O(N Log N) - Серия увеличение подпоследовательности

Answer 9

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

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


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