2. Часть 2

Created Friday 10 October 2014

http://habrahabr.ru/post/195482/

Сложность

Линейный поиск

<?php
$exists = false;
for ($i = 0; $i < n; ++$i) {
if ($A[$i] == $value) {
$exists = true;
break;
}
}
?>
f(n) = n

Квадрат

bool duplicate = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j && A[i] == A[j]) {
duplicate = true;
break;
}
}
if (duplicate) {
break;
}
}
f(n) = n^2

Практическая рекомендация

Система обозначений

Нотация "большое О" — верхняя граница сложности

b = []
n.times do
m = a[0]
mi = 0
a.each_with_index do [element, i]
if element < m
m = element
mi = i
end
end
a.delete_at(mi)
b << m
end

Ω-нотация — нижняя граница сложности

Строгие (O и Ω) и не строгие (o и ω) границы

Оператор сравнения асимптотических оценок Оператор сравнения чисел
Алгоритм является o( что-то ) Число < чего-то
Алгоритм является O( что-то ) Число ≤ чего-то
Алгоритм является Θ( что-то ) Число = чему-то
Алгоритм является Ω( что-то ) Число ≥ чего-то
Алгоритм является ω( что-то ) Число > чего-то



Backlinks: