Big O против определения типа функции - PullRequest
Новая
       86

Big O против определения типа функции

0 голосов
/ 21 октября 2018

Я пытаюсь определить правильные имена (определения) для следующих пунктов.

Допустим, algorithm 1 имеет временную сложность, подобную этой: 

T1(n) = 5 * n^2 + n + 123 = O(n^2)

Как я долженНазовите алгоритм, который имеет такую ​​сложность?Правильно ли говорить, что алгоритм имеет quadratic complexity type или algorithm type is quadratic или algorithm is quadratic complexity class?

Я использую слово type, потому что согласно этой статье , если у нас есть такая функция, как: 

T(n) = n^2

Мы говорим, что функция имеет квадратичный тип.

Я думаю, что слово class абсолютно неверно, поскольку классы сложности связаны с проблемами NP, NL и т. Д.

Теперь предположим, что у нас есть algorithm 2 со сложностью, подобной этой:

T2(n) = 2 * log n + 15 = O(log n)

ОБНОВЛЕНИЕ: Итак, вопрос в следующем: правильно ли говорить, что алгоритмы 1 и 2 имеют разные types or classes or something else сложности?Какое слово подходит?

ОБНОВЛЕНИЕ 2: Давайте представим следующее.Вы говорите со своим другом Бобом и говорите: Боб, первый алгоритм имеет квадратичную сложность, а второй - логарифмическую сложность.Итак, Боб, как ты видишь, у этих алгоритмов разные сложности ...?Какое слово вы должны использовать вместо ...?Types или classes или, может быть, что-то еще?

Проблема в том, что английский не является моим родным языком, и для меня почти невозможно найти правильные определения, когда мы говорим о сложностях.Потому что все, что я могу сделать, это попытаться перевести это с моего языка, но мой язык даже не имеет этих определений.

1 Ответ

0 голосов
/ 21 октября 2018

O(n^2) - квадратичная сложность времени.Вы можете обратиться к этой вики-странице для более подробного объяснения различных временных сложностей.

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

Дополнительная информация:

Алгоритм будет иметь сложность пространства и сложность времени.

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

Алгоритм с квадратичной временной сложностью O(n^2) будет иметь время выполнения, пропорциональное квадрату n.(например, сортировка по пузырькам)

Время выполнения алгоритма с логарифмической сложностью O(log n) будет пропорционально логу n.(например, бинарный поиск)

Оба этих класса имеют детерминированные времена, поэтому они будут в классе сложности P.

Иллюстрация времени выполнения:

O(n) - лучший алгоритм, чем O(n^2).Возможно, что O(n^2) будет работать лучше, чем O(n) алгоритм до определенного n.Но по мере увеличения n * O(n^2) будет медленнее, чем алгоритм O(n).

Пример: 

T1(n) = 5 * n = O(n)
T2(n) = 9999*n = O(n)
T3(n) = n^2 = O(n^2)

Случай 1: n = 10 

T1 takes 5*10 = 50 sec
T2 takes 9999*10 = 99990 sec
T3 takes 10 * 10 = 100 sec

T3 работает лучше, чем T2, даже если он O(n^2).

Случай 2: n = 100 

T1 takes 5*100 = 500 sec
T2 takes 9999*100 = 999900 sec
T3 takes 100 * 100 = 10000 sec

T3 работает лучше, чем T2, даже если он равен O(n^2).

Случай 3: n = 10000 

T1 takes 5*10000 = 50000 sec
T2 takes 9999*10000 = 99990000 sec
T3 takes 10000 * 10000 = 100000000 sec

Теперь T2 работает лучше, чем T3.Для всех n> 10000 T2 будет работать лучше, чем T3.

...