Предположим, что у вас есть два алгоритма (A1 и A2)Выбор, какой алгоритм использовать
A1 = Omega(n)
A2 = O(n^2)
эти алгоритмы определяет число п, является ли простое число или нет. Какой из них выбрать и почему?
, а также при выполнении теста на большом количестве с A1 и A2 не отмечено разницы в рабочем времени. Как это возможно?
Эти алгоритмы определяют, является ли число n простым числом или нет. Какой из них выбрать и почему?
Предоставленная спецификация алгоритмов недостаточно информативна по нескольким причинам.
O (n^2) и Omega (n) недостаточно информативны для выбора, который имеет лучшую асимптотическую сложность. Например, вы можете выполнить A1 в Theta(n), а A2 работает в Theta(n^2), а A1 будет асимптотически лучше, чем A2. С другой стороны, вы можете использовать A1 в Theta(n^3), а A2 - в Theta(log^3(n)) (which is the best known algorithm for testing primality of a number). В зависимости от того, какая из них - истинная сложность - ответ будет варьироваться.
Кроме того, мы ничего не знаем о ожидаемых вводах, если ожидаемые входы представляют собой небольшие значения n - обозначение большой O (и большая Омега) не очень информативны, поскольку они обрабатывают только большие значения.
Однако 2-й действительно дает вам некоторую верхнюю границу, в то время как первая не делает, так что это бонус. Хотя все еще недостаточно, чтобы точно определить, что лучше.
. Ordo = Big O? Что такое Omega и Big O для A2 и A1 соответственно? Каковы алгоритмы? –
@ C.B. Я никогда не видел, чтобы это было написано так, а не как O(), но wikipedia указывает, что это так. (Скорее, страница disambig для «Ordo» указывает, что это так - страница на ноте Big O не упоминает ничего об этом.) – neminem
Я имею в виду Ordo (n^2), O (n^2), а также I не получили никаких алгоритмов, но предположим. – Simon