Расчет времени выполнения

Question

Я застрял в следующей задаче, которую мне удалось решить в первой части, однако я не уверен, что делать дальше:

сколько раз печатает следующая программаиз "Привет"?То есть какое время работы?(в терминах обозначения Big-O)

int i = 1;
int j = 1;
while(i <= n )
{
    j+= j;
   int k = 1;
   while (k <= j)
    {
       System.out.println("Hi");
       k = k +1;
    }
    i = i + 1;
}

Мне удалось сделать вывод, что программа выдаст Суммирование от x = 1 до n (2 ^ x) суммыего.Это также время выполнения или я должен разбить код на две суммы, где одно от i = 1 до n, а другое .... (я не знаю).Спасибо за помощь!

Answer 1

Ваше время выполнения в виде суммирования выглядит правильно.Тогда вопрос в том, как вы это упростите.К счастью, у нас есть этот факт:

2 ⁰ + 2 ¹ + 2 ² + ... + 2 ^n-1 = 2 ⁿ - 1.

Игнорирование каких-либо отдельных ошибок при замене этой суммы на вашу сумму, что мы можем сделать благодарязапись big-O, мы видим, что «Hello!» распечатывается Θ (2 ⁿ ) раз.

Answer 2

Тогда вы можете попробовать вот так

    int i = 1;
    int j = 1;
    long startTime = System.nanoTime();
    while(i <= n )
    {
        j+= j;
       int k = 1;
       while (k <= j)
        {
           System.out.println("Hi");
           k = k +1;
        }
        i = i + 1;
    }
    long endTime = System.nanoTime();
    System.out.println("time taken in nano seconds" + endTime-startTime);