Худший случай Runtime наивного алгоритма

Question

Я не уверен, как рассчитать наихудшее время выполнения алгоритма. Я знаком с асимптотической нотацией, но не уверен, как ее использовать. Один из примеров для объяснения может быть:

d = (X1 - X2)^2 + (Y1 - Y2)^2 
for i=1 to N-1 do: 
    for j=i+1 to n do: 
    t = (Xi - Xj)^2 + (Yi - Yj)^2 
    if (t < d) then d = t 
return d 

Это имеет входы набора N точек (X1, Y1) .... (Xn, Yn) с N> = 2. Выходом должно быть квадратное расстояние ближайшей пары точек. Как вычислить время выполнения этого?

Answer 1

Алгоритм берет все возможные пары из входов N. Существует n (n-1)/2 таких пар, что является числом раз, когда выполняется внутренняя часть внутреннего цикла. Предполагая, что арифметические операции являются постоянными во времени, временной сложностью является, таким образом, O (n²).

Обратите внимание, что не существует неизвестный фактор в этом алгоритме, который влияет на сложность времени, так что это как лучший & худшем случае временная сложность: θ (n²)