Блог

Как мне найти нотацию big O для этого алгоритма?

Вот что я получил: O(n logn 1) Я очень не уверен в своем ответе, потому что я знаю только, как найти временную сложность с помощью циклов for. Но этот отличается от того, что я знаю.

для цикла for я знаю, что когда задан диапазон, вы можете использовать суммирование, чтобы вычислить, сколько раз цикл повторяется, но диапазон не указан, просто индекс.

Я был бы очень признателен, если бы кто-нибудь мог помочь мне найти общее время выполнения каждой строки кода.

 Find Base(N,B)   // N>=1 and B>=2
    index <- 0
    while N > 0 do                              
       A[index] <- N % B         
       N <- N / B                         
       index <- index   1              O(logn)     
    for j = 0 to index do                
       temp <- A[j]
       A[j] <- A[index – j]
       A[index – j] <- temp
return A
 

Я предварю этот ответ оговоркой о том, что в этом ответе не будет абсолютно никакой математической строгости. Иногда вы сталкиваетесь с тем, что не можете просто посмотреть на что-то и извлечь из этого полезную сложность во время выполнения — вот тогда вы оставляете это в покое и переходите к реальной строгой математике. Это не так часто требуется для многих из нас.

Если вы хотите провести строгий математический анализ, сделайте это самостоятельно.

Оставив это в стороне, давайте перейдем к быстрому и грязному асимптотическому анализу сложности времени выполнения. Мы в основном просто подсчитываем, сколько мы все делаем.

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

Для этого примера мне нужно добавить одно неустановленное предположение. Произвольный доступ к A для чтения и записи — это постоянное время. Очевидно, что существуют структуры данных, которые опровергают это предположение, поэтому мы должны четко понимать это.

 Find Base(N,B)   // N>=1 and B>=2    
    index <- 0                       // O(1) - assign constant to a local
    while N > 0 do                              
       A[index] <- N % B             // O(1) - calculate division remainder,
                                     //        array random access write
       N <- N / B                    // O(1) - calculate integer division,
                                     //        assign to local
       index <- index   1            // O(1) - addition,
                                     //        assign to local
    for j = 0 to index do                
       temp <- A[j]                  // O(1) - array random access read,
                                     //        assign to local
       A[j] <- A[index – j]          // O(1) - array random access read,
                                     // O(1)   array random access write
       A[index – j] <- temp          // O(1) - array random access write
return A
 

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

Я начинаю со второго цикла.

     for j = 0 to index do                
       \some O(1) operations that don't modify anything that affects the loop condition.
 

Выполняется ровно index 1 раз, O(1) каждый раз что-то делая. На каждом шаге мы можем просто превратить это в среду выполнения Big-O. Вырежьте все постоянные факторы и недоминирующие термины: это O(index) . Нам все еще нужно выяснить, что index такое в терминах N и B , поэтому мы будем иметь это в виду.

Первый цикл

     while N > 0 do                              
       A[index] <- N % B         
       N <- N / B                         
       index <- index   1
 

Мы уже выяснили, что все тело цикла равно O(1) . Теперь нам нужно знать, сколько раз он выполняется в терминах N и B . Сначала определите, какой шаг фактически приводит к его завершению. Присвоение переменным, используемым в условии цикла, и все, что вносит вклад в значение, вычисленное для этого присвоения, имеет значение.

Эта строка N <- N / B . Это делится N на B и присваивает ему пол N . Мы должны продолжать делать это до N тех пор, пока значение не станет равным 0 (или отрицательным — но продолжающееся деление положительного числа на положительное число> 1 достигает 0, а не отрицательных значений). Таким образом, для каждой итерации цикла N есть значения N , N/B , N/(B^2) и т.д. Итак, это деление на B, пока мы больше не сможем. Поэтому, когда N/(B^t) < 1, цикл завершается. Это происходит, когда N < (B^t) . Если бы это было равенство, вместо t этого, естественно, было бы Log (base B ) of N . Итак, чтобы сделать ближайшее целочисленное неравенство, мы можем просто заполнить и добавить 1, что дает нам t = floor(log_b(N)) 1 . Таким образом, цикл выполняется примерно log_b(N) раз. Но поскольку нас интересует только асимптотическая сложность для Big-O, мы будем игнорировать точные границы и то, будет ли это на одну итерацию больше или меньше, чем логарифм или нет. Мы даже проигнорируем всю базу логарифма *. Это выполняется O(log(N)) несколько раз. Он выполняет O(1) операции каждый раз, поэтому, умножая их вместе, мы получаем O(log(N)) общее.

Общее время выполнения — это просто сумма двух циклов, которые выполняются один за другим: O(log(N)) O(index)

Вернемся к этому досадному index . он начинается с 0, увеличивается на 1 на каждой итерации первого цикла. Мы определили, что существуют O(log(N)) итерации этого цикла. Таким образом, значение index равно O(log(N)) . Так O(index) и есть O(log(N)) . Предыдущая сумма теперь имеет постоянный множитель, который мы можем забыть, поэтому общая сумма равна O(log(N))

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

Что-то, с чем следует быть осторожным, здесь не было. Иногда тело цикла может выполнять разное количество на каждой итерации, поэтому сложение каждой итерации не так просто, как просто умножение, которое было здесь. Иногда вы получаете линейные или геометрические ряды из них, и вам нужно вставить немного реальной математики в середину быстрого и грязного анализа.

* Преобразование между базами логарифмов — это просто умножение на постоянный множитель. Поскольку мы игнорируем умножение на константу в Big-O, O(log(n)) оно одинаково для всех логарифмических оснований.