alex-rogov
commented
5 years ago Big O notation применяется во время указания сложности алгоритма. Если быть точнее, Big O указывает на худший случай, при котором может работать программа.
O(1) показывает то, что алгоритм выполняется за линейный промежуток времени, при этом не зависит от количества или размеров начальных данных. Это демонстрирует код ниже.
private static bool IsFirstElementNullOrEmpty(List elems)
{
if (elems.Count > 0)
{
return string.IsNullOrEmpty(elems[0]));
}
return false;
}O(N) При O(N) производительность алгоритма растет пропорционально размеру заданных данных. Код ниже показывает худший случай выполнения программы. Big O notation всегда будет принимать верхний лимит где алгоритм демонстрирует максимальное количество итераций.
private static bool ContainsValue(List elems, string missingElement)
{
if (elems.Count > 0)
{
for (int i = 0; i< elems.Count; i++)
{
if (elems[i].Equals(missingElement))
{
return true;
}
}
}
return false;
}Классическим примером O(N 2) сложности является Bubble Sort. Алгоритм сравнивает каждый элемент со следующим в списке и меняет их местами, если нужно. В конечном итоге, самый большой элемент будет лидирующим в списке. Худший сценарий O(N 2).
private static int[] BubbleSort(int[] array)
{
for (int i = array.Length - 1; i >= 0; i--)
{
for (int j = 1; j<= i; j++)
{
if (array[j- 1] > array[j])
{
int temp = array[j- 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
return array;
}Вот визуальное представление о том, как формируется сложность алгоритма сортировки Bubble Sort.
vkrasiy
alexzhyshko
FairyFox5700
WalrusPUNCH
IlliaKov
NikitaViktorov
crowl1
AleksAndriushyn
galaxyair
BogdanDudnik
Comparison of theoretical complexity (big-O) with practical measurements Сравнение теоретической сложности (big-O) с практическими измерениями Порівняння теоретичної складності (big-O) з практичними вимірами
Resources that compare theoretical estimates of the complexity of algorithms with practical measurements Measurement details should be provided Availability of the benchmark code (to run and compare with published results) -Extra points for actually running them and comparing with published results
Ресурсы, где сравнивают теоретические оценки сложности алгоритмов с конкретными измерениями Желательно, чтобы были детали измерений И код benchmarks, который можно запустить и сравнить -Дополнительные баллы тем, кто запустит код у себя и сравнит результаты с опубликованными
Ресурси, де порівнюють теоретичні оцінки складності алгоритмів з конкретними вимірами Бажано, щоб були деталі вимірів Та код benchmarks, який можна запустити та порівняти -Додаткові бали тим, хто запустить на своїх пристроях та порівняє результати з опублікованими