Нужно объяснение GRE Big-O нотации вопрос

Question

Я ищу объяснение этого вопроса, так как я учусь на GRE:

Алгоритм запускается за 10 секунд для записи размера 50.Если алгоритм является квадратичным, сколько времени он тратит примерно на один и тот же компьютер, если вход имеет размер 100?

Я не вижу связи между временем и входом,

Учитывая: O(n^2) -> O(50^2) =! 10 (seconds)

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

Спасибо.

Answer 1

Big-O не информирует вас о точной корреляции между размером записи и временем выполнения, но вместо этого сообщает приблизительную корреляцию между увеличением размера записи и увеличением времени выполнения.Итак: O(n) сложность означает, что размер записи и время выполнения прямо пропорциональны (если ввод в 3 раза больше, то время выполнения также будет в 3 раза больше), O(n^2) означает, что если размер записи равенВ 3 раза больше, тогда время выполнения будет в 9 раз больше и т. Д.

В вашем случае начальное время выполнения для записи размера 50 составляет 10 секунд.Если входное значение изменяется на запись размера 100, то, просто разделив, мы можем сказать, что оно в 100 / 50 = 2 раз больше.Зная, что алгоритм Big-O равен O(n^2), мы можем сказать, что время выполнения будет в 2^2 = 4 раз больше.Таким образом, если начальное время выполнения составляло 10 секунд, то время выполнения для большего ввода будет приблизительно 10 seconds * 4 = 40 seconds.

Связанный вопрос SO: Грубая оценка времени выполнения из Big O

Хорошая статья о биг-о: https://rob -bell.net / 2009/06 / a-beginners-guide-to-big-o-notation /

Answer 2

Обратите внимание, что терминология неаккуратна, сложность времени не имеет понятия времени (да, имя обманчиво).

---

Пренебрежение терминами меньше, чем O (n ² ), поскольку мы работаем в рамках структуры Big-O, квадратичная функция может быть выражена как

t = c * n ²

Учитывая пару (t, n) со значением (10, 50) weиметь

10 = c *2500* 1030 * c = 1/250 = 4/1000

Решение для (т,100) мы получаем

t = 4/1000 * 10000 = 40

---

Существует более быстрый и более проницательный способ решения этой проблемы.
Тренированный глаз может сразу определить ответ как 40.

Считайте, что эта функция является степенной функцией:

t = c * n ^k

Теперь давайте рассмотрим входы m ₀ и m ₁ , с m ₁ = a * m ₀ , кратное m ₀ .
Позволяет сравнить соответствующие т ₀ , т ₁ :

т ₀ = c * ( m ₀ ) ^k
t ₁ = c * ( m ₁ ) ^k = c * a ^k * ( m ₀ ) ^k

Итак, мы видим, что для полиномиальной функции времени t ₁ / t ₀ = a ^k или t ₁ = a ^k * t ₀ .

Соотношение между двумя выходами равносоотношение между их входами, к k-й мощность .

Для квадратичной функции k = 2, таким образом, соотношение между двумя выходами является квадратом отношения между двумя входами.
Если вход удваивается (отношение = 2), то выходв четыре раза (отношение = 2 ² = 4).
Если входное значение утроится (отношение = 3), выход будет девять -кратным (отношение = 3 ² = 9)

Хорошая мнемоническая уловка - помнить, что функция от отношения входов к отношению выходов имеет тот же тип заданной функции.
Нам дана квадратичная функция, так что это тип отношениймежду соотношениями входов и выходов:

input   output
ratio   ratio
 1       1
 2       4
 3       9
 4       16
 5       25
...      ...

Проблема говорит вам, что выход удваивается (от 50 до 100 записей), поэтому выход должен быть в четыре раза (от 10 до 40), так как функция квадратичная.
Как видите, все данные задачи используются элегантно и без каких-либо жестких вычислений.

---

Предполагается, что сторонние источники не одобряются, но в этом случае я не могу не рекомендовать прочитать:

• Введение в теоретические вычисления -Майкл Сипсер

---

Посмотрите, сможете ли вы ответить на следующие вопросы:

• Если сейчас ввод 150 записей, сколько времени это займет?
• Если на входе сейчас 30 записей, сколько времени это займет?
• Если на входе теперь 100 записей, но программа запускается на компьютере, который в два раза быстрее, сколько времени это займет?
• Какой размер ввода необходим для запуска программы не менее 1000 секунд?

Answer 3

Учитывая сложность времени, вы не можете рассчитать точное время выполнения (в секундах) алгоритма.Тем не менее, он дает хорошее представление о скорости роста измеренного времени.

В алгоритме с линейным временем (O (n)) ожидается, что время будет линейно увеличиваться как функция от входа.Например, если для обработки 10000 элементов на каком-либо компьютере требуется одна секунда, то следует ожидать, что для 50000 элементов потребуется около 5 секунд и т. Д.Это не так в квадратичном алгоритме (O (n ^ 2)), который «наказывает» вас больше, когда размер ввода больше;увеличение размера ввода в 2 раза приведет к увеличению времени обработки в 4 раза, увеличение размера ввода в 5 раз приведет к увеличению времени обработки в 25 раз и т. д. (точно так же, как ведет себя функция F (x) = x ^ 2).

Вы можете использовать этот пост как введение, а этот как более формальное объяснение.