Я решил попробовать решить проблему наихудшего времени выполнения алгоритма и немного попрактиковаться.
Поскольку я новичок, мне нужна только помощь в правильном выражении своего ответа.
Я столкнулся с этой проблемой в книге, в которой используется следующий алгоритм:
Ввод: набор из n точек (x1, y1),. , , , (xn, yn) с n ≥ 2.
Вывод: квадрат расстояния ближайшей пары точек.
ClosePoints
1. if n = 2 then return (x1 − x2)^2 + (y1 − y2)^2
2. else
3. d ← 0
4. for i ← 1 to n − 1 do
5. for j ← i + 1 to n do
6. t ← (xi − xj)^2 + (yi − yj)^2
7. if t < d then
8. d ← t
9. return d
Мой вопрос заключается в том, как я могу предложить хорошее доказательство того, что T (n) = O (n ^ 2), T (n) = Ω (n ^ 2) и T (n) = Θ (n ^ 2)? где T (n) представляет наихудшее возможное время выполнения.
Я знаю, что мы говорим, что F является O (г),
тогда и только тогда, когда существует такое n0 ∈ N и c> 0 в R, что для всех
n ≥ n0 мы имеем
f (n) ≤ cg (n).
А также мы говорим, что f это Ω (g), если есть
n0 ∈ N и c> 0 в R так, что для всех n ≥ n0 имеем
f (n) ≥ cg (n).
Теперь я знаю, что алгоритм выполняет c * n (n - 1) итераций, давая T (n) = c * n ^ 2 - c * n.
Первые 3 строки выполняются O (1) раз по 4 циклам цикла для n - 1 итераций, что составляет O (n). Строка 5 циклов для n - i итераций, что также равно O (n). Делает каждую строку содержимого внутреннего цикла
(строки 6-7) принимает (n-1) (ni) или просто O (1)? и почему? Единственное изменение - это сколько раз выполняется 8. (d ← t), но оно должно быть меньше или равно O (N ^ 2).
Итак, как мне написать хорошее и полное доказательство того, что T (n) = O (n ^ 2), T (n) = Ω (n ^ 2) и T (n) = Θ (n ^ 2) ?
Заранее спасибо