Оценка эффективности алгоритмов по памяти и времени. Вычисление веса двоичного вектора

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
Последовательность х – n-мерный двоичный вектор с элементами xi
W(x) – вес вектора х – число его ненулевых элементов
Найти вес двоичного вектора
Задача

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
1 способ – последовательное рассмотрение элементов вектора и сравнение их с нулем. Аналогично записи:
Это решение методом перебора.
Имея конечное число элементов,
рассматриваем их один за другим, при
этом выполняя сравнение с нулем.

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
Определения
Обозначение О(…) является оценкой сложности алгоритма
если
n – размерность задачи
g(n) – некоторая известная функция (линейная, степенная, логарифмическая и пр.)
f(n) – сложность алгоритма (может рассматриваться число некоторых элементарных действий или объем данных)

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
Определения
Анализ сложности с точки зрения О(…) позволяет лишь оценить скорость роста функции f(n), т.е. нельзя определить точное значение числа шагов или ячеек памяти
Такой анализ используется для сравнения двух алгоритмов, при оценке их реализуемости.
Возвращаемся к задаче
Найти вес двоичного вектора

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
1 способ – метод перебора. Требуется выполнить (n-1) сложений, размер требуемой памяти не изменяется с изменением n.
Т.е. сложность данного алгоритма O(n) по времени и O(1) по памяти
Переформулируем постановку задачи
Существует ли более эффективный способ вычисления веса двоичного вектора,
при котором сложность по времени будет меньше, чем O(n)

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
2 способ – предвычисление веса для всех возможных наборов двоичных векторов длины n.

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
2 способ – предвычисление веса для всех возможных наборов двоичных векторов длины n.
В общем случае объем такой таблицы составить 2n ячеек памяти, для вычисления вектора нужна одна операция – обращение к таблице.
Снизили временную сложность до О(1)
Увеличили сложность по памяти до О(2n)
т.е. неравноценно меняем время на память

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
3 способ
Операция , где х – десятичное представление двоичного набора (x1,…xn)
приводит к тому, что обнуляется самая правая единица, т.е. кол-во единиц становится на 1 меньше
10010100
1
_________
10010011
10010100
_________
10010000
-
˄
Тогда решить задачу можно за W(x) шагов,
каждый раз сравнивая результат вычисления с 0
Каждый шаг это 4 операции: вычитание, побитовое умножение, увеличение счетчика, сравнение с нулем
Сложность такого алгоритма O(W(x)) по времени и O(1) по памяти

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
4 способ
переборный по времени алгоритм (1 способ) требовал (n-1) сложение
3
2
1
1
1
1
0
1
0
0
1
0
1
0
0
Листья – элементы вектора
Корень – сумма всех элементов
Появляется идея уменьшения числа сложений
Уменьшение сложности вычислений

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
Пусть x = 10010100
Складываем элементы на соседних позициях
3
2
1
1
1
1
0
1
0
0
1
0
1
0
0
Выделим из x позиции, имеющие четные и нечетные номера: умножим побитово вектор x на двоичную маску
и сдвинем результат на 1 бит вправо

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
Пусть x = 10010100
Сумма десятичных представлений xнч1 и xч1
даст вектор
3
2
1
1
1
1
0
1
0
0
1
0
1
0
0
В десятичном представлении это последовательность
За одно десятичное сложение n-битных чисел выполнили n/2 сложений однобитных чисел

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
Пусть x = 10010100
Аналогично за одно сложение можно вычислить результат второго уровня
3
2
1
1
1
1
0
1
0
0
1
0
1
0
0
и сдвинем результат на 2 бита вправо

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
Пусть x = 10010100
Последний шаг
3
2
1
1
1
1
0
1
0
0
1
0
1
0
0
и сдвинем результат на 4 бита вправо
Ответ: W(x) = 3

Оценка эффективности алгоритмов по памяти и времени
Вычисление веса двоичного вектора
4й способ требует столько сложений, сколько уровней содержит дерево, это дает временную сложность O(log n).
Нашли решение задачи, гораздо более эффективное, чем переборные методы