Линейное время v.s. Квадратичное время

Ответ 1

Метод линейный, когда требуемое время линейно возрастает с числом задействованных элементов. Например, цикл for, который печатает элементы массива, примерно линейный:

for x in range(10):
    print x

потому что, если мы напечатаем диапазон (100) вместо диапазона (10), время, которое потребуется для его запуска, в 10 раз больше. Вы увидите очень часто, что написано как O (N), что означает, что время или вычислительные усилия для запуска алгоритма пропорциональны N.

Теперь предположим, что мы хотим напечатать элементы двух циклов:

for x in range(10):
    for y in range(10):
        print x, y

Для каждого x, я иду 10 раз цикла y. По этой причине все это проходит через 10x10 = 100 отпечатков (вы можете увидеть их, просто запустив код). Если вместо использования 10, я использую 100, теперь метод будет делать 100x100 = 10000. Другими словами, метод идет как O (N * N) или O (N²), потому что каждый раз, когда вы увеличиваете количество элементов, вычислительная сила или время будут увеличиваться как квадрат числа точек.

Ответ 2

Они должны ссылаться на сложность во время выполнения, также известную как нотация Big O. Это чрезвычайно важная тема для решения проблемы. Я бы начал со статьи по википедии: https://en.wikipedia.org/wiki/Big_O_notation

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

Понимание того, как классифицировать сложность выполнения алгоритма во время выполнения, даст вам представление о том, как ваш алгоритм будет масштабироваться с точки зрения времени или памяти. Это даст вам возможность свободно сравнивать и классифицировать алгоритмы друг с другом.

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

Вот некоторые типичные порядки роста:

• O (1) - постоянное время
• O (log n) - логарифмический
• O (n) - линейное время
• O (n ^ 2) - квадратичный
• O (2 ^ n) - экспоненциальный
• O (n!) - factorial

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

Удачи!

Ответ 3

Обычно вы утверждаете об алгоритме с точки зрения размера ввода n (если вход представляет собой массив или список). Линейным решением проблемы будет алгоритм, время выполнения которого линеаризуется с помощью n, поэтому x*n + y, где x и y являются действительными числами. n появляется с наивысшим показателем 1: n = n^1.

С квадратичным решением n появляется в члене с 2 как наивысший показатель степени, например. x*n^2 + y*n + z.

При произвольном n линейное решение растет во время выполнения гораздо медленнее, чем квадратичное.

Для получения дополнительной информации посмотрите Big O Notation.

Ответ 4

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

 x(n) <= c * x(n-1)^2

для некоторой положительной константы c. То есть ошибка в решении на итерации n+1 меньше квадрата ошибки на итерации n. См. Это для более полного введения для более общих определений скорости конвергенции http://en.wikipedia.org/wiki/Rate_of_convergence