Нахождение временной сложности этого метода - PullRequest
Новая
       72

Нахождение временной сложности этого метода

0 голосов
/ 11 июня 2018

Я пытаюсь выяснить временную сложность этого кода.

Мой последний вывод о разделах заключается в том, что секция 'while' O (logn) внешнего цикла for должна быть меньше 100, поэтому егоO (1), а внутренним циклом for является O (logn), поэтому я думаю, что сложность времени здесь O (logn) в худшем случае, но я не уверен. 

public void foo (int n, int m) {
    int i = m;

    while (i > 100) {
        i = i/3;
    }

    for (int k=i ; k>=0; k--) {
        for (int j=1; j<n; j*=2) {
            System.out.print(k + "\t" + j);
        }

        System.out.println();
    }
}

1 Ответ

0 голосов
/ 11 июня 2018

Позволяет пошагово разбить ваш код:

Первый цикл, т. Е. 

 while (i > 100)  
     i = i/3;

выполняется O (logm) раз. 

for (int k=i ; k>=0; k--) { 
        for (int j=1; j<n; j*=2) {
            System.out.print(k + "\t" + j); 
        } //end inner for loop
        System.out.println(); 
    }

Внешний циклможет выполняться максимум 100 раз, а внутренний цикл, т. е. 

for (int j=1; j<n; j*=2) {
      System.out.print(k + "\t" + j); 
} //end inner for loop

, выполняет время входа в систему.

общая сложность времени для циклов for = 100logn -> игнорирование констант -> logn

Следовательно, сложность O (log (m)) + O (log (n))

...