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

Question

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

а) (n) = 9n+6

б) (n) = 2(n^2)+1

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

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

Я думаю, что это А. Я прав?

А каков ответ на часть B? Что именно они хотят?

Answer 1

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

Чтобы ответить на этот вопрос, вам просто нужно взглянуть на показатели 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. </p>

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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 2 (n ^ 2) + 1 = 33

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

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

Answer 6

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

Answer 7

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

Доказательство оставлено в качестве упражнения для читателя.

Answer 8

Ответ на первую часть, очевидно, (а), потому что O (n * n)> O (n).

Ответ на вторую часть заключается в том, что вы не можете сказать «что лучше для небольших входных размеров», потому что вы не даете никакой информации о том, что такое «элементарные операции» в каждом случае, и о том, сколько времени занимает каждая из этих операций. Компилятор или процессор могут применить некоторую оптимизацию, которая заставляет так называемый более медленный алгоритм выполнять НАМНОГО быстрее, чем «лучший» алгоритм при небольших входных размерах.

И «маленькими» размерами ввода, которые могут означать 10, 100 или 1 миллион +! Пересечение между умным алгоритмом O (n) и алгоритмом немого O (n * n) может быть огромным, потому что компиляторы и процессоры отлично справляются с очень быстрой работой тупого кода.

Многие люди совершают ошибку, «оптимизируя» свой код на основе O (), не принимая во внимание размер ввода и не проверяя, насколько хорошо каждый работает с наборами данных, которые они будут использовать.

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

Answer 9

очевидно, если мы имеем: * 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 намного лучше.

Answer 10

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