Помощь в изучении основы алгоритма

Question

Я изучаю алгоритмы и нуждаюсь в вас, ребята, чтобы помочь мне. Я новичок, поэтому простите меня, если мой вопрос не ясен. Я понимаю, что вижу что-то вроде NlogN, N^2 и т. Д. И что-то в этом роде.

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

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

Благодарим за помощь.

Kap.

Answer 1

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

Answer 2

Купить Introduction to Algorithms. Вы можете получить подержанную версию по доступной цене.

И/или вид эти great online video lectures от MIT, построенный вокруг вышеупомянутой книги.

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

Answer 3

То, что вы описали, называется big O notation. Here - руководство, объясняющее это.

Важно отметить, что нотация игнорирует незначительные термины. Если ваш алгоритм выполняет 6X^2 + 3X + 12 секунд для выполнения, где X - количество обрабатываемых точек данных, просто назовите его O (X^2), потому что, когда X становится большим, 6 не будут действительно иметь значение , а также не будет 3 или 12.

Answer 4

http://www.amazon.com/Structures-Algorithm-Analysis-Allen-Weiss/dp/0805390529 - одна из лучших книг, которые отлично объяснят алгоритмы.

--Cheers

Answer 5

Вы говорите о записи Big-O. Эта нотация - это способ описания наихудшего времени работы алгоритма в зависимости от его размера ввода.

O (n^2) означает, что если вход имеет размер n (такой как список с n элементами в нем), алгоритм потребует n^2 прохождения для выполнения в наихудшем случае сценарий (Big-O в худшем случае, есть другие обозначения для случая наилучшего случая и среднего). Это может произойти, если у вас есть петля for for, вложенная внутри другой, и оба выполняются от 1 до n.

O (nlogn) аналогичен. Обычно это происходит, когда вы просматриваете древовидную структуру (например, двоичное дерево).

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

Многие из других уже разместили хорошие ссылки для чтения.