sfd
Оценка сложности алгоритмов: зачем нужна большая "О"
Вы, вероятно, встречали в материалах, связанных с программированием, что-то похожее на O(n) или O(log n). Если вы знаете, что это, то дальше можете не читать. В противном случае вы, наверное, просто пропускали эти буквы мимо, так как либо не понимали, о чём речь, либо вас это просто не интересовало. Во всяком случае, так я и делал. Знать об этом, однако, очень полезно как в концептуальном, так и в практическом плане. Каждый раз, когда мы пишем алгоритм, у него есть какая-то сложность. Что нужно о ней знать? Предположим, вы суммируете элементы одномерного массива размером N...
Вычисление асимптотической сложности алгоритма Часть I. Основные понятия.
Нередко, читая описание какого либо алгоритма можно наткнуться на вычисление его асимптотической сложности, для новичка не всегда понятно что это такое. В данной статье мы дадим точное определение и разберем наиболее частые виды асимптотической сложности, а во второй части, которая выйдет завтра познакомимся с правилами ее вычисления. Асимптотическая сложность (производительность) алгоритма определяется функцией, которая указывает, насколько ухудшается работа алгоритма с усложнением поставленной задачи...