Асимптотический анализ против Big O - PullRequest
Новая
       11

Асимптотический анализ против Big O

0 голосов
/ 20 сентября 2018

Рассмотрим следующую функцию: 

int foo(int n) {
  int x = 0;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        x -= 1;
    }
  }

  x = 0;

  for(int i = 0; i < n; i++) {
    x += 1;
  }
  return x;
}

В соответствии с обозначением Big O, сложность этой функции во время выполнения будет (я буду очень точен): 

O(1 + N^2 + 1 + N) = O(N^2)

Зависимость между N и верхней границей времени выполнения алгоритма равна: 

1 + N^2 + 1 + N

Согласно этой статье , Асимптотический анализ позволяет отбросить константы и недоминантные члены.Таким образом, зависимость от результата будет: 

1 + N^2 + 1 + N = N^2

Это то же выражение, что и для обозначения Big O.

Но согласно эта лекция Асимптотический анализ не позволяет намчтобы отбросить константы, а также недоминантные термины, поэтому, если я захочу оценить это выражение с помощью асимптотического анализа, я получу: 

1 + N^2 + 1 + N

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

  1. Какая разница между нотацией Big O и асимптотическим анализом?
  2. Какая из двух статей лжёт?

1 Ответ

0 голосов
/ 02 апреля 2019

Какая разница между нотацией Big O и асимптотическим анализом?

Асимптотический анализ - это метод для нас, чтобы проанализировать, является ли один алгоритм «быстрее», чем другой, если его время выполнения масштабируется лучше сразмер ввода.И он просто подходит для большого ввода, но он может абстрагироваться от внешних факторов, которые могут повлиять на скорость алгоритма, таких как аппаратные средства, язык и другие проблемы.

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

Но как мы можем сравнить производительность двух алгоритмов?Есть три меры: Big O, Big Omega и Big Theta.Для подробного объяснения, пожалуйста, обратитесь к этот ответ .

Какая из двух статей лжёт?

Думаю, вы получили ответ в комментариях.

...