Обозначение сложности алгоритма - PullRequest
Новая
       3

Обозначение сложности алгоритма

1 голос
/ 29 мая 2020

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

function test(int x, int y, int N){
  int i, j, k;
  if (x==y) {
   for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++) {
        commands here
      }
   }
   for (i = 0; i < N; i++) {
     commands here
   }
  }else {
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
           for (k = 0; k < N; k++) {
              commands here
           }
       }
    }
  }
}

Я проанализировал следующее:

f (x, y, n) = n² + n (если x = y)

f (x, y, n) = n³ (если x ≠ y)

Это означает, что в наилучшем сценарии , f (n) = n² + n или просто O (n²) и в наихудшем сценарии , f (n) = n³ или просто O (n³)

Мой вопрос: Я правильно понимаю? Понимание того, какая функция больше, является интуитивным, но нужно ли мне математически сравнивать обе функции, чтобы доказать это? Кроме того, модуль правильный?

Спасибо, ребята!

1 Ответ

3 голосов
/ 29 мая 2020

Если предположить, что «команды здесь» выполняются в постоянное время, тогда вы правы.

Вы описываете кусочную временную сложность для данного алгоритма, зависящую от значений x и y. Вы правильно разбили два случая и проанализировали их сложность, снова предполагая, что «команды» являются постоянными по времени. Теперь, чтобы сравнить два случая более строго:

Показать, что последний случай, (x!=y), асимптотически больше, чем первый, (x==y), и, следовательно, является наихудшим случаем, так же просто, как показать, что N^3 не меньше N^2 для всех значений N, превышающих определенное значение. Поскольку N^3 больше N^2 для всех значений, по крайней мере, 0, мы можем сказать, что N^2 = O(N^3) и, следовательно, O(N^3) на самом деле является худшим из двух случаев и, следовательно, наихудшим временем выполнения. Можно применить аргумент симметрии c, чтобы показать, что другой случай является оптимальной средой выполнения.

Вы можете показать то же самое быстрее, взяв предел одной среды выполнения, разделенной на другую как N уходит в бесконечность. Если этот предел достигает 0, то числитель = O (знаменатель), а если он стремится к бесконечности, то верно обратное. Если он переходит в некоторую положительную константу, то они имеют одинаковую асимптотическую c сложность, выраженную нотацией омега.

краткий обзор асимптотики c нотация

Вы могли бы погрузиться в анализ среднего случая, если бы знали что-нибудь о распределениях X и Y, поскольку вы сможете определить вероятность того, что произойдет худший / лучший случай.

...