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

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

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

Answer 1

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

Answer 2

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

1) Действительно ли этот вопрос говорит о O (n), O (nlogn), O (n^ 2) когда они действительно имеют в виду Тета (n), Тета (nlogn) и Тета (n ^ 2)?

2)

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

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

Answer 3

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

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 4

Вот как будет выглядеть их сюжет

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

Answer 5

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

Answer 6

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

Answer 7

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