Как судить относительную эффективность алгоритмов, данных время выполнения как функции 'n'?

Я думаю, что построение этих функций было бы очень полезно для понимания того, что происходит.

Простое графическое программное обеспечение покажет, что 9n + 6 будет работать лучше довольно быстро. как и простая алгебра. В подходах из 5 и более подходов 9n + 6 будет быстрее.

Посмотрев на константы, легко увидеть, что вначале a будет больше, чем b. Глядя на вхождения n (n в a, n ^ 2 в b), вы можете увидеть, что b асимптотически больше. Таким образом, нам нужно только выяснить, из какой точки b больше, чем a. Для этого нам просто нужно решить уравнение a (n) = b (n) относительно n.

Я бы запустил алгоритм несколько раз для описанных вами случаев (и на компьютерах с разными процессорами) и узнал время начала и время окончания. Затем посмотрите на разницу их времени для каждого из ваших случаев.

9n + 6 - лучший вариант.

Возьмем этот пример, если ваше n равно 10, тогда

9n + 6 = 96 2 (n ^ 2) + 1 = 201

, возьмем, что n равно 100

9n + 6 = 906 2 (n ^ 2) + 1 = 20001

и это продолжается и продолжается ...

если n = 4, то

9n + 6 = 40 {{1 }} 2 (n ^ 2) + 1 = 33

Заключение, второй вариант лучше, если n <= 4, но хуже, если 5 или больше.

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

это очевидно, если у нас есть: * 9n + 6 => n: 5 => 9 * 5 + 6 = 45 + 6 = 51 * 2 (n ^ 2) +1 => n: 5 => 2 (5 * 5) +1 = 2 * 25 + 1 = 50 + 1 = 51 , затем 9n + 6 намного лучше.

Какой алгоритм является лучшим асимптотически?

Чтобы ответить на этот вопрос, вам просто нужно взглянуть на экспоненты n в обеих функциях: Асимптотически n ² будет расти быстрее, чем n . Таким образом, A ∈ O ( n ) асимптотически лучший выбор, чем B ∈ O ( n ² ).

Что лучше всего для небольших входных данных n , и для каких значений n это так? (При необходимости вы можете предположить, что n > 0.)

Чтобы ответить на этот вопрос, вам нужно найти точку пересечения, в которой обе функции имеют одинаковое значение. А для n = 5 обе функции вычисляют 51 (см. 9n + 6 = 2 (n ^ 2) +1 в Wolfram Alpha ). А поскольку A (4) = 42 и B (4) = 33, B - лучший выбор для n <5.

Асимптотически O (n) лучше (дешевле), чем O (n ^ 2).

Для малых значений n это простая задача алгебры:

Найдите n, для которого 9n + 6 = 2 (n ^ 2) +1 : очистив его, мы получим уравнение 2-го класса 2 (n ^ 2) -9n-5 = 0 . Это дает n = 5, что означает, что для n = 5 оба процесса будут иметь одинаковую стоимость:

• 9n + 6 => n: 5 => 9 * 5 + 6 = 45 + 6 = 51
• 2 (n ^ 2) +1 => n: 5 => 2 (5 * 5) +1 = 2 * 25 + 1 = 50 + 1 = 51

Это означает, что B лучше для n <5, они равны при n = 5, а A лучше при n> 5. Если вы ожидаете, что n будет меньше 5 в подавляющем большинстве случаев, тогда B может быть лучшим выбором, но это будет актуально только в том случае, если алгоритм используется много . Если вы реализуете его как функцию, незначительные преимущества B бледнеют по сравнению с накладными расходами на вызовы, поэтому они не будут незаметными.

Таким образом, если вы не совсем уверены в своих намерениях, переходите к A. В общем, вам всегда нужен алгоритм с лучшей (более дешевой) асимптотической стоимостью. Только когда у вас одинаковый общий порядок или если у вас есть надежные знания о входных данных, которые вы можете получить, более глубокое понимание стоит усилий, и даже в этом случае лучший подход - это сравнительный анализ обеих версий с реалистичными данными, чем теоретический анализ.

Вам, вероятно, следует начать с ознакомления с асимптотикой, обозначением большой буквы O и т.п. Асимптотически будет лучше. Почему? Поскольку можно доказать, что для достаточно большого N, a (n) N.