Найти эффективность в нотации Big-O

Question

У меня возникла проблема со следующим вопросом:

Рассмотрите следующую конструкцию вложенной петли. Обозначьте его эффективность в терминах переменной с использованием обозначения «большой о». Предположим, что операторы, представленные эллипсисом (...), требуют четырех основных обращений к памяти (каждый из которых требует одну микросекунду) и два файла доступа к файлам (каждый из которых требует одну миллисекунду). Экспресс в миллисекундах количество времени эта конструкция потребовала бы выполнить, если п было 1000.

x = 1; 
do 
{ 
    y = n; 
    while (y > 0) 
    { 
    ... 
     y--; 
    } 
    x *= 2; 
} while (x < n*n); 

Answer 1

Внутренний контур с у = О (п).

Наружная петля работает с x = 1, 2, 2^2, 2^3, ... 2^k < n * n. Следовательно, он работает в O (журнал (п * п)), который является O (2 * журнал (п))

Следовательно, сложность O (N * журнала (п))

Answer 2

Просто добавить еще какое-то объяснение к другому ответу, заметной частью кода является x * = 2; т.е. удвоение. Таким образом, эта часть не является линейной. Поэтому вы должны думать log2.

Следовательно, x достигнет n * n в log2 (n * n). = log2 (n^2) = 2 x log2 (n).

Y-обратный отсчет времени линейно - таким образом, что представляет собой О (п)

Существует цикл внутри цикла, так что вы умножить обе операции, как в:

N * 2 х log2 (п) = О (n * 2 * log2 (n)). Затем вы вынимаете постоянные факторы: O (n * log2 (n))