Большое количество операций

Question

Как вы вычисляете количество операций, которое будет выполнять каждая строка кода.

Пример.

Algorithm find2D (A,x)
    arrLength = A.length
    for j <- 1 to arrLength – 1 do
         for k <- 1 to arrLength – 1 do
                if A[j][k] = x then
                  return true
          increment k
    increment j
return false

Я придумал этот псевдокод.Поэтому я не совсем уверен, как посчитать количество операций, выполняемых каждой строкой кода.

Так, как в первом цикле было бы 1 + n операций, так как вы должны установить j, сравните j с arrLength -1, и он будет повторяться n-1 раз.Так что это дает вам n-1 + 1 + 1, что равно n + 1 операциям.

Так что для второго цикла это будет то же самое, даже если оно вложено.

Янемного запутался в сравнении A[j][k] = x, сколько бы это было операций.

Спасибо.

Answer 1

Общее правило таково:

Для каждого цикла, в котором вы проходите каждый элемент массива, умножьте его на N

.по log (N)

Поскольку у вас есть два вложенных цикла по всему массиву, вы O (N ^ 2).

Вычислить постоянный коэффициент сложнее и зависит от деталейязыка, компилятора и оборудования.В основном, просто нужно решить это эмпирически.

Answer 2

Big-Oh является асимптотическим, поэтому вам не следует беспокоиться о «1» в «1 + n».

Если все, что вам нужно, это классификация Big-Oh этого кодапросто учтите, что у вас есть два цикла, один вложен в другой, и каждый цикл выполняет некоторое постоянное число операций на элемент.Тогда внутренний цикл равен O (n), а внешний цикл выполняет внутренний цикл n раз, поэтому внешний цикл равен O (n ^ 2).Тогда вся функция равна O (c + n ^ 2), где c - это постоянное число операций из кода, окружающего внешний цикл.Поскольку Big-Oh является асимптотическим, c исчезает, а ваша функция равна O (n ^ 2).

Если вы пытаетесь вычислить точное число операций, выполняемых кодом, вам, вероятно, потребуетсякакую абстрактную машину вы используете.

Надеюсь, это поможет.

Answer 3

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