java: Big-Oh порядок этого фрагмента кода do-while? Плюс плотная верхняя граница

Question

Я знаю, что это легко, но в моем учебнике не говорится о заказе Big-Oh с циклами do-while, и ни один из моих других источников алгоритмов.

Эта проблема утверждает, что следующий фрагмент кода параметризуется в переменной «n» и что требуется также жесткая верхняя граница.

int i=0, j=0; 

do { 

    do { 

      System.out.println("...looping..."); //growth should be measured in calls to println. 

      j=j+5; 

     } while (j < n); 

    i++; 

    j = 0; 

} while (i < n); 

Может ли кто-нибудь помочь мне с этим и объяснить порядок Big-Oh с точки зрения циклов do-while? Являются ли они такими же, как для циклов?

Answer 1

Хороший афоризм для работы с вложенными циклами и большой-O является

«В случае сомнений, работа изнутри!»

Вот код, который вы выложили:

int i=0, j=0; 
do { 
    do { 
      Do something 
      j=j+5; 
    } while (j < n); 
    i++; 
    j = 0; 
} while (i < n); 

Давайте посмотрим на этот внутренний цикл. Он работает примерно n/5 раз, так как j начинается с 0 и увеличивается на пять на каждом шаге. (Мы также видим, что j всегда возвращается к 0 до начала цикла, либо вне цикла, либо по завершении внутреннего цикла). Таким образом, мы можем заменить внутренний цикл с чем-то, что в основном говорит «делать Θ (N) операций, которые мы заботимся о том,» как это:

int i=0; 
do { 
    do Θ(n) operations that we care about; 
    i++; 
} while (i < n); 

Теперь мы просто должны видеть, как много работы, это делает. Обратите внимание, что это будет цикл Θ (n) раз, так как я считает 0, 1, 2, ..., до n. Чистый эффект заключается в том, что этот цикл выполняется Θ (n) раз, и так как мы выполняем операции Θ (n), которые мы волнуем на каждой итерации, чистый эффект заключается в том, что это Θ (n) распечаток, который вы пытаетесь подсчитать.