сложность времени функции повторения с оператором if-else - PullRequest
Новая
       12

сложность времени функции повторения с оператором if-else

2 голосов
/ 24 сентября 2019

У меня возникли проблемы с решением временной сложности функции, указанной ниже. 

pubilc static long powerN(long x, int n){
      if(n==0) return 1;
      if(n%2 == 0){
            long a = powerN(x, n/2);
            return a*a;
      }
      else {
            long a = powerN(x, (n-1)/2);
            return a*a;
      }

}

Я узнал, что если есть оператор if, мы усложняем оператор then / else.

В вышеприведенном примере сложность времени обоих условных операторов одинакова, поэтому я пришел к выводу следующим образом.

Предположим, что powerN функции будет T (n), 

T(n) = T(n/2) + k (k is the overhead)

, поэтому я пришел к выводуСложность времени T (n) составляет O(logn).

Но я все еще задаюсь вопросом, верны ли мои предположения.Спасибо.

1 Ответ

1 голос
/ 24 сентября 2019

Ваше предположение в основном верно, по крайней мере, в этом случае.

Как правило, вам необходимо проверить значение оператора if-else и частоту его запуска.Если одна ветвь if-else вызывается так же часто, как другая (или лучше сказать сложность, такая же частая, как и другая), то ее вызов, т.е. в 10 раз больше, не меняет сложности. Вызов if-branch k times больше, чем else-branchесли k является константой, то это хорошо. Вызов, т. е. * в 1005 * раз больше, влияет на сложность).

Просто представьте, что выражение if будет следующим: 

public static long powerN(long x, int n){
      if(n==0) return 1;
      if(n < 100){
            long a = powerN(x, n-1);
            return a*a;
      }
      else {
            long a = powerN(x, (n-1)/2);
            return a*a;
      }

}

Тогда в основномif-branch работает в постоянное время для n <100, и вы должны его игнорировать. </p>

Или представьте себе следующее: это будет работать с T(n/2) до n = log(N) и затем T(n-1) для log(N)время.Тогда вы просто не сможете просто взять ветку if-else «что внутри» и выбрать большую. 

long initialN = 10000;
long intialX = 500;
powerN(initialX, initialN);

public static long powerN(long x, int n){
      if(n==0) return 1;
      if(n > log(initialN) ){
            long a = powerN(x, n/2);
            return a*a;
      }
      else {
            long a = powerN(x, n-1);
            return a*a;
      }

}
...