Каковы некоторые алгоритмы, которые мы используем ежедневно, которые имеют O (1), O (n log n) и O (log n) сложности?Примеры алгоритмов, которые имеют O (1), O (n log n) и O (log n) сложности
ответ
Если вы хотите примеры алгоритмов/группы операторов с временной сложностью, как указано в вопросе, вот небольшой список -
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.
Надеюсь, это хорошо ответит на ваш вопрос. Если у пользователей есть больше примеров для добавления, я буду более чем счастлив :)
Что относительно n !? Мне было интересно, какой общий алгоритм использует n !? –
Доступ к значению HashMap, а также более сложные алгоритмы, такие как реализация LRU, которые достигают O (1) с использованием HashMap и дважды связанного списка или реализации стека с функциями PUSH/POP/MIN. Также рекурсивная реализация Фибоначчи относится к N !. – ruralcoder
Кроме того, нахождение a^n равно O (log n). Хороший пример в вступлении Ляна в книгу программирования java – oiyio
Сложность прикладного программного обеспечения не измеряется и не записывается в нотации большого О. Полезно только измерять сложность алгоритма и сравнивать алгоритмы в той же области. Скорее всего, когда мы говорим O (n), мы имеем в виду, что это «O (n) сравнения» или «O (n) арифметические операции». Это означает, что вы не можете сравнивать любую пару алгоритмов или приложений.
Это не так. Если алгоритм имеет сложность времени O (N), это означает, что его время выполнения ограничено шагами k * N для некоторой константы k. Не важно, являются ли «этапы» циклы CPU, инструкции по сборке или (простые) операции C. Эти детали скрыты константой k. –
Не говоря уже о том, что во многих практических случаях «c» алгоритма O (logN) делает его хуже, чем более простой алгоритм O (N). – Zed
Ха-ха, да, и мы будем обозначать длину ввода на ленте машины Тьюринга, которая делает вертикальную форму деления для экспоненциального времени. :-) Каждый домен имеет свои собственные требования и собственный участок абстрагирования. –
Я могу предложить вам некоторые общие алгоритмы ...
- O (1): Доступ к элементу в массиве (т.е. Int я = а [9])
- O (п журнал п) : быстро или слияние (в среднем)
- O (журнал N): Двоичный поиск
Они будут ответами кишки, как это звучит как домашнее задание/интервью рода вопрос. Если вы ищете что-то более конкретное, это немного сложнее, поскольку общественность вообще не имела бы представления о базовой реализации (с открытым исходным кодом, конечно) популярного приложения, а также вообще не относится к «приложению»
Простой пример O(1)
может быть return 23;
- независимо от ввода, это вернется в фиксированное, конечное время.
Типичный пример O(N log N)
будет сортировать входной массив с хорошим алгоритмом (например, mergesort).
Типичный пример, если O(log N)
будет искать значение в сортированном массиве ввода путем деления пополам.
O (n log n) - это верхняя граница того, как быстро вы можете сортировать произвольный набор (предполагая стандартную и непараллельную вычислительную модель).
O (1): найти лучший следующий шаг в шахматах (или, если на то пошло). Поскольку число состояний игры ограничено, это только O (1) :-)
Да, вы обычно можете торговать временем для космоса. Я на самом деле сделал это для игры с tic-tac-toe, поскольку есть только 3^9 состояний (меньше, если вы обрабатываете вращение разумно). Шахматы, тем не менее, имеют несколько большее количество состояний :-) – paxdiablo
O (1) - большинство процедур приготовления - это O (1), то есть требуется постоянное количество времени, даже если есть больше люди готовят (в некоторой степени, потому что вы можете выбежать из своего места в кастрюле/сковороде и разделить кулинарию)
O (logn) - найти что-то в телефонной книге. Думайте о двоичном поиске.
O (n) - чтение книги, где n - количество страниц. Это минимальное время, затрачиваемое на чтение книги.
O (nlogn) - не может сразу подумать о чем-то, что каждый может сделать каждый день, что это nlogn ... если вы не сортируете карты, делая слияние или быстро сортировать!
Потребуется намного больше времени, чтобы приготовить жаркое, чем мини-жаркое :-) – paxdiablo
, но обычно требуется то же самое время, чтобы приготовить два мини-жаркого против одного мини- жареный, при условии, что ваша духовка достаточно велика, чтобы вписаться в нее! – Chii
Touche. Хорошая точка зрения. – paxdiablo
Вы можете добавить следующие алгоритмы в списке:
O(1)
- Определение, является ли число четным или нечетным; Работа с HashMap
O(logN)
- вычисления х^N,
O(N Log N)
- Серия увеличение подпоследовательности
O (1) - Удаление элемента из двусвязного списка. например
typedef struct _node {
struct _node *next;
struct _node *prev;
int data;
} node;
void delete(node **head, node *to_delete)
{
.
.
.
}
Сделайте это wiki, пожалуйста. –
Почему wiki? Это ни опрос, ни субъективность. Ей нужны конкретные примеры свойств большого О. – paxdiablo
Wiki, потому что у него нет единого правильного ответа, у него есть несколько ответов. –