Идентификация того алгоритма, который и объясняет время работы

Question

Для данной задачи с размером ввода n выполнены алгоритмы A, B, C. В терминах времени работы один из алгоритмов: O (n), один O (nlogn) и один O (n^2). Некоторые измеренные времена работы этих алгоритмов приведены ниже

      Input Size 
        512   1024   2048 

      A  70   134    262 
      B  135   517    2053 
      C  42   86    182 

Определите, какой алгоритм является и объясняет наблюдаемое время работы. Какой алгоритм вы выбрали бы для разных значений n

Пожалуйста, помогите мне с вышеуказанным вопросом. Thanks

Answer 1

График производительности трех алгоритмов - тогда будет очевидна временная сложность.

Answer 2

Посмотрите на коэффициенты ввода и время вычислений.

Answer 3

Удостоверяются, что вы поняли термины nlogn, n^2 и n. Рассмотрим построение этих функций для понимания взаимосвязи между входом и выходом. Ответ будет очевиден, если вы поймете эти отношения.

Answer 4

Нарисуйте графики из 3 наборов данных. Сравните с темпом роста графиков для n, nlogn ... Вы увидите.

Answer 5

Это то, что их сюжет будет выглядеть

Теперь, если вы понимаете, что time complexity подразумевает и как графики п, п и NlogN будет выглядеть как , это не должно быть сложно.

Answer 6

Часто я обнаружил, что самым простым способом сравнения сложностей было «нормализовать» результаты.

Input Size:  1  2  4 
Algorithm A:  1  1.91 3.74 
Algorithm C:  1  2.04 4.33 
Algorithm B:  1  3.82 15.21 

Эта таблица просто получается путем определения каждой строки по ее минимуму (первый элемент в этом случае).

Затем я переупорядочил строки от медленно растущего до быстрорастущего: можете ли вы угадать сложность каждого из алгоритмов?

PS: шпаргалка для n log n, только для проверки приближения

Input Size  Time 
n    n log n 
2*n    2 * n * (log n + log 2) 
4*n    4 * n * (log n + 2 * log 2) 

Answer 7

Этот вопрос оставляет меня с удивлением: что есть учителя, которые задают такого рода фиктивных и вводящим в заблуждение вопросы.

1) Разве вопрос действительно говорил о O (n), O (nlogn), O (n^2), когда они действительно означают Theta (n), Theta (nlogn) и Theta (n^2)?

2)

Всего три точки данных (или 9 всего) не является достаточным, чтобы отличить, что есть что.

Мы можем выбрать соответствующие константы, чтобы A, B, C могли быть любыми из трех, которые мы хотим.