188
правок
Изменения
Нет описания правки
</wikitex>
=== Оптимизация с помощью битовых масок ===
Строки матрицы <tex>W</tex> можно хранить с помощью массива битовых масок длиной <tex>k</tex>. Тогда последний цикл будет выполняться в <tex>k</tex> раз быстрее и сложность алгоритма снижается до <tex>O\Big(\fracdfrac{n^3}{k}\Big)</tex>. <br>
Пример реализации оптимизации с помощью битмасок:
W[i][j] = W[i][j] '''or''' W[k][j]
В данной реализации длина битовой маски <tex>k</tex> равна <tex>32 </tex> битам. Последний цикл делает в <tex>32 </tex> раза меньше операций {{---}} сложность алгоритма <tex>O\Big(\fracdfrac{n^3}{32}\Big)</tex>.
== Источники информации ==
