Я попытался сравнить два алгоритма, которые ищут уникальный элемент в списке. Далее для пропуска всяких проверок, допускается, что список всегда содержит более 3 элементов и элементы могут быть только 1 или 2.
#!/usr/bin/env python3
import timeit
def find_uniq_1(arr):
''' итоговая сложность: O(n) | время выполнения: 0.002494273998308927 '''
a, b = set(arr) #O(len(arr))
return a if arr.count(a) == 1 else b # O(n)
mock = [1 for x in range(100000)]
mock.extend([ 1, 1, 1, 2, 1, 1 ])
start = timeit.default_timer()
print(find_uniq_1(mock))
stop = timeit.default_timer()
print('Time for find_uniq_1: ', stop - start)
def find_uniq_2(arr):
''' итоговая сложность: O(n) | время выполнения: 0.01582404098007828 '''
first = arr[0] # O(1)
left = [] # O(1)
right = [] # O(1)
for n in arr: # O(n)
if n == first:
left.append(n) # O(1)
else:
right.append(n) # O(1)
return right[0] if len(left) > 1 else left[0] # O(1)
mock = [1 for x in range(100000)]
mock.extend([ 1, 1, 1, 2, 1, 1 ])
start = timeit.default_timer()
print(find_uniq_2(mock))
stop = timeit.default_timer()
print('Time for find_uniq_2: ', stop - start)
В результате измерения времени выполнения видно, что первый алгоритм на порядок быстрее. Нормальная ли это ситуация когда два алгоритма с одинаковой сложностью имеют время выполнения, которое различается на порядок?
Я понимаю, что многое зависит от железа, но порядок это вполне конкретный показатель. И если у сложности в О-нотации такая большая погрешность, то нужно ли вообще заморачиваться со сложностью алгоритма?
