Определите время выполнения функции:

Question

public static void p2(int N) { 
  for (int i = 0; i < N; i += 1) { 
    for (int j = 1; j < N; j = j * 2) {  
        System.out.println("hi !"); 
    } 
  } 
}

Можете ли вы помочь мне определить время выполнения этой функции?

Я попытался найти какую-то схему для различных входов N. Я рассчитал затраты для входов до 5 (println использовался длядля этих целей):

N: 0, 1, 2, 3, 4, 5

C (N): 0, 0, 2, 6, 8, 15

Где C (N) - функция стоимости.

Однако я не знаю, что делать дальше!Ответ Θ (N log (N))

Answer 1

Внутренний цикл будет выполняться lg n раз.Вы можете понять это, посмотрев, сколько раз вы поделите N на 2, чтобы получить 1?(т.е. сколько раз будет выполняться внутренний цикл?) Ответ на этот вопрос lg n.И внешний цикл будет работать N раза.Таким образом, для каждой итерации i внутренний цикл будет выполняться lg n раз.Это означает, что вложенный цикл будет выполняться ровно n(lgn) раз, что является временной сложностью этого вопроса.