Примеры Алгоритмов, который имеет O (1), O (n регистрируют n), и O (регистрируют n), сложности
Сделайте две общественных собственности ConnectionString и FileName и затем используйте их для заполнения объекта.
В C# можно использовать объект initalizer. Как это:
Thing thing = new Thing{FileName = "abc", ConnectionString = "123"};
8 ответов
Простым примером O (1) может быть return 23; - независимо от ввода, это вернется за фиксированное конечное время .
Типичный пример O (N log N) - это сортировка входного массива с помощью хорошего алгоритма (например, сортировка слиянием).
Типичный пример, если O (log N) будет искать значение в отсортированном входном массиве пополам.
O (1) - большинство процедур приготовления - это O (1), то есть на это требуется постоянное количество времени, даже если есть больше людей, для которых нужно готовить (в определенной степени, потому что вы может закончиться место в вашей кастрюле / сковороде, и вам потребуется разделить готовку)
O (logn) - найти что-то в телефонной книге. Подумайте о двоичном поиске.
O (n) - чтение книги, где n - количество страниц. Это минимальное количество времени, необходимое для чтения книги.
O (nlogn) - не могу сразу придумать что-то, что можно делать каждый день, что является nlogn ... если только вы не отсортируете карточки, выполнив слияние или быструю сортировку!
Я могу предложить вам несколько общих алгоритмов ...
- O (1): Доступ к элементу в массиве (т.е. int i = a [9])
- O (n log n): быстрая сортировка или сортировка слиянием (в среднем)
- O (log n): двоичный поиск
Это будут интуитивные ответы, поскольку это звучит как вопрос типа домашнего задания / интервью. Если вы ищете что-то более конкретное, это немного сложнее, поскольку общественность в целом не будет иметь представления о базовой реализации (конечно, с сохранением открытого исходного кода) популярного приложения, и эта концепция в целом не применима к «приложению»
O (1) - Удаление элемента из двусвязного списка. например,
typedef struct _node {
struct _node *next;
struct _node *prev;
int data;
} node;
void delete(node **head, node *to_delete)
{
.
.
.
}
Сложность программного приложения не измеряется и не записывается в нотации большого О. Полезно только измерять сложность алгоритма и сравнивать алгоритмы в одной и той же области. Скорее всего, когда мы говорим O (n), мы имеем в виду, что это «O (n) сравнений » или «O (n) арифметических операций». Это означает, что вы не можете сравнивать никакую пару алгоритмов или приложений.
You can add following algorithms to your list:
O(1) - Determining if a number is even or odd; Working with HashMap
O(logN) - computing x^N,
O(N Log N) - Longest increasing subsequence
O (n log n) - известная верхняя граница того, насколько быстро вы можете отсортировать произвольный набор (при условии стандартной, а не высокопараллельной модели вычислений).
O (1): найти лучший следующий ход в шахматах (или в го). Поскольку количество состояний игры конечно, оно составляет всего O (1): -)