Я расскажу, что это домашнее задание, но я не ищу типичную домашнюю работу. Я просто хочу подтвердить формулировку вопроса. В вопросе говорится, что мой алгоритм должен быть линейным по числу вершин в графе. Я никогда не видел эту формулировку, просто говорю, что мое время работы должно быть O (| V |)? Если так, я думаю, у меня есть мое решение.Анализ подтверждения нотации алгоритмов
При анализе алгоритмов алгоритмы классифицируются по эффективности как функция их размера ввода.
O(|V|) означает, что ваш алгоритм должен проверять или «касаться» каждой вершины вашего графика. Так что да, линейное число вершин означает O(|V|).
Для справки: Большой O, Ɵ, или Ω; две вертикальные полосы означают номер. Они также используются для обозначения длины в некоторых доказательствах.
Благодарим за быстрый ответ. – Pinsickle
@Pinsickle Нет проблем, если вы работаете с этим типом вещей, возможно, стоит купить эту книгу: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 своего рода стандарт для анализа алгоритмов и структур данных. –
'' должен проверять или «касаться» каждой вершины «' - технически немного упрощения/обобщения. Вы * можете * написать алгоритм для обработки первых '| V |' * ребер * (и никогда не касаться вершины), и это также будет 'O (| V |)'. Важная часть состоит в том, что выполняется постоянная работа на вершину. Кроме того, '' две вертикальные полосы ''не * просто * означают мощность (число) в Big O, Ɵ или Ω. Вы можете использовать его в любом месте, чтобы указать мощность. – Dukeling
Да, вы правы. – vidit
@ vidit Спасибо, я надеялся, что я это услышу. – Pinsickle