1. Часть 1

Created Friday 10 October 2014
http://habrahabr.ru/post/196560/

Подсчёт инструкций

Найдём максимальный элемент в массиве

var M = A[0];
for (var i = 0; i < n; ++i) {
if (A[i] >= M) {
M = A[i];
}
}

Подсчёт фундаментальных инструкций

Предположим, что наш процессор способен выполнять как единые инструкции следующие операции:
Пусть ветвление происходит мгновенно

Aсимптотическое поведение

Отбрасываем те элементы функции, которые при росте n возрастают медленно, и оставляем только те, что растут быстро



Backlinks: