анализ алгоритма

Question

, почему мы всегда учитываем большое значение входных данных при анализе алгоритма, например, для обозначения big-oh?

Answer 1

Смысл Big-O нотации состоит в том, чтобы точно определить, как время работы (или пространство) изменяется с увеличением размера ввода - другими словами, насколько хорошо оно масштабируется.

Если вас интересуют только небольшие входные данные, вам не следует использовать анализ Big-O ... кроме всего прочего, часто есть подходы, которые действительно плохо масштабируются, но работают очень хорошо для небольших входных данных.

Answer 2

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

Answer 3

Предположим, мы хотим проверить, является ли no простым или нет.И Рам и Шиам придумали следующие решения.

Решение Рама

   for(int i = 2; i <= n-1; i++) 
            if( n % i == 0 )
                return false;
         return true;

Теперь мы знаем, что приведенный выше алгоритм будет работать n-2 раза.

Решение Шиама

 for(int i = 2; i <= sqrt(n); i++)
   if ( n % i == 0 )
     return false;
 return true;

Приведенный выше алгоритм будет запускаться sqrt (n) - 1 раз

Если предположить, что в обоих алгоритмах каждый цикл занимает единицу времени (1 мс), то

если n = 101

1-й алгоритм : - принятое время составляет 99 мс, что даже меньше, чем моргание глаза

2-й алгоритм : - около 9 мс, что опять-таки не заметно.

, если n = 10000000019

1-й алгоритм : - принятое время составляет 115 дней , что3-й год.

2-й алгоритм : - Примерно 1,66 минуты, что эквивалентно потягиванию чашки кофе.

Думаю, сейчас ничего не нужно говорить:D

Answer 4

Big O ничего не говорит о как хорошо алгоритм будет масштабироваться. «Насколько хорошо» относительно. Это общий способ количественной оценки масштабирования алгоритма, но пригодность или отсутствие пригодности для какой-либо конкретной цели не является частью обозначения.

Answer 5

Это из-за определения нотации BigO. Учитывая, что O (f (n)) является границами для g ([размер списка n]): для некоторого значения n, n0, всех значений n, n0

Это означает, что после того, как ваш ввод превысит определенный размер, функция не будет масштабироваться за пределами какой-либо функции. Таким образом, если f (x) = x (т.е. eq to O (n)), n2 = 2 * n1, вычисляемая мной функция не займет вдвое больше времени. Теперь обратите внимание, что если O (n) верно, то и O (n ^ 2). Если моя функция никогда не будет хуже, чем double, она никогда не будет хуже, чем квадрат. На практике обычно дается самая низкая известная функция порядка.

Answer 6

Анализ алгоритмов означает не просто запуск их на компьютере, чтобы увидеть, какой из них быстрее.Скорее это возможность взглянуть на алгоритм и определить, как он будет работать.Это делается путем просмотра порядка величины алгоритма.Поскольку количество элементов (N) изменяется, как оно влияет на количество операций, необходимых для выполнения (время).Этот метод классификации называется обозначением BIG-O.

Программисты используют Big-O, чтобы получить приблизительную оценку «сколько секунд» и «сколько памяти» используют разные алгоритмы для «большого«входы