Блок проверки грамматических ошибок с открытым исходным кодом [закрывается]

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

Несколько примеров того, как это используется в коде C.

Говорят, что у нас есть массив n элементов

int array[n];

, Если бы мы хотели получить доступ к первому элементу массива, то это было бы O (1), так как не имеет значения, насколько большой массив, всегда требуется то же постоянное время для получения первого объекта.

x = array[0];

, Если мы хотели найти число в списке:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

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

, Когда мы добираемся до вложенных циклов:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Это - O (n^2) с тех пор для каждой передачи внешнего цикла (O (n)), мы должны пройти весь список снова, таким образом, n's умножается, отъезд нас с n придал квадратную форму.

Это едва царапает поверхность, но когда Вы добираетесь до анализа более сложной математики комплекса алгоритмов, включающей доказательства, играет роль. Надежда это ознакомляет Вас с основами, по крайней мере, все же.