Вікіпедія

Метод чотирьох росіян: відмінності між версіями

Інтерактивний перегляд історії
[перевірена версія][перевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
SOMBot (обговорення | внесок)
Боти
166 258 редагувань
м ізольована стаття сирота0
м Заміна застарілого математичного синтаксису відповідно до mw:Extension:Math/Roadmap
Рядок 19:
Щоб обчислити <math>Q = AB</math>, можна зробити наступне.
 
Для <math>j \in [1 .. \frac{n}{\epsilon \log n}]</math> : <math>Q_{ij} = Q_{ik} \orlor (A_{ij}\cdot B_j^k)</math> (за означенням булевого добутку матриць). Таким чином, час потрібний для виконання алгоритму становить
:<math>O\left(n\cdot\frac{n}{\log n}^2 \cdot \log n\right) = O\left(\frac{n^3}{\log n}\right)</math>.
 
Передобчисливши всі можливі побітові <math>\orlor</math> у таблицю <math>S</math> так, що <math>S(u, v) = u \orlor v</math>, де <math>u, v \in \{0,1\}^{\epsilon\log n}</math>, можна зменшити час виконання до <math>O\left(\frac{n^3}{\log^2 n}\right)</math>.
 
== Історія ==
Отримано з https://uk.wikipedia.org/wiki/Метод_чотирьох_росіян