Python. Простые алгоритмы

a = 5
b = 15
c = 25

Способ №1. Использование оператора if else

if a > b:
   if a > c:
       print(a)
   else:
       print(c)
else:
   if b > c:
       print(b)
   else:
       print(c)
#25
Временная сложность: O(1)– постоянная временная сложность

Пояснения

• O(1) означает постоянное время выполнения. Независимо от размера входных данных алгоритм будет иметь одинаковое время выполнения.
• Нотация большого «О» используется не для оценки конкретного времени работы кода. Ее используют для оценки того, как быстро возрастает время обработки данных алгоритмом в привязке к объему этих данных.
• Временная сложность алгоритма определяет число шагов, которые должен предпринять алгоритм, в зависимости от объема входящих данных (n).

Способ №2. Использование оператора elif

if a > c and a > b : print(a)
elif b > a and b > c : print(b)
else: print(c)
#25
Временная сложность: O(1)

Способ №3. Использование дополнительной переменной

mx = a
if b > mx:
     mx = b
if c > mx:
     mx = c
print(mx)
#25
Временная сложность: O (1)

Способ №4. Использование функции max()

mx = max(a,b,c)
print(mx)
#25
Временная сложность: O (1)

Способ №5. Использование функции сортировки sorted()

m = sorted([a,b,c])
print(m[-1])
#25
Временная сложность: O(n log n),

 

В Python в алгоритмах сортировки используется алгоритм Timsort, временная сложность которого определяется зависимость O(n log n), где n– количество элементов в списке.

a = [1,2,3,4]

Способ № 1 использование цикла for

 for x in a:
   print(x, end = ' ')

#1 2 3 4

Временная сложность: O (n)

 

Способ № 2 использование цикла For и range

for i in range(len(a)):
   print(a[i], end = ' ')

#1 2 3 4

Временная сложность: O (n)

 

Способ № 3 использование цикла while

n = len(a)
i = 0
while i<n:
   print(a[i], end=' ')
   i+=1

#1 2 3 4

Временная сложность: O (n)

 

Способ № 4. Использование генератора списка

[print(x, end = ' ') for x in a]

#1 2 3 4

Временная сложность: O (n)

  

Способ № 5. Использование enumerate()

for i, item in enumerate(a):
   print (item, end =' ')

#1 2 3 4

Временная сложность: O (n)

Способ № 6. Использование iterate()

Итерируемый объект – это такой объект, элементы которого можно перебрать. Например, последовательность. Итератор – это специальный объект, который перебирает элементы итерируемого объекта.

Если нам нужно извлечь какое-либо значение из списка или строки, то следует использовать индексы или срезы. Но если необходимо перебирать итерируемые объекты самых разных типов, то единственный универсальный и безопасный способ это сделать – использовать итераторы. 

Пример использования итератора для просмотра списка

it = iter(a)
try:
   while True:
       x = next(it)
       print(x, end=' ')
except StopIteration:
   pass

#1 2 3 4

Временная сложность: O(n)

Для оценки производительности способов итерации по числовому списку будем использовать   модуль timeit.

Измерения производятся с помощью класса Timer. Конструктор класса имеет следующий формат:

timeit.repeat(stmt, setup, number, repeat)

В параметрах указываются:

• stmt - код (в виде строки), время выполнения которого необходимо измерить
• setup - указывается код (в виде строки), который будет выполнен перед измерением времени выполнения кода в параметре stmt
• number – указывается количество повторений. Если параметр не задан, то по умолчанию равен 1_000_000
• Метод timeit.repeat вызывает метод timeit() указанное в параметре repeat количество раз и возвращает список значений.

Для оценки производительности способов итерации по числовому списку создадим список из 10 000 элементов перед измерением затраченного времени для каждого способа.

Каждый способ повторим 1000 раз, а затем создадим список из 5 запусков timeit и найдем минимальное значение в этом списке. Так мы получим оценочное время выполнения способов итерации по числовому списку.

Вот код:

import timeit
setup = """
a = [x for x in range(10_000) ]
# """

Способ_1 = """
for x in a:
     z=x
"""
Способ_2 = """
for i in range(len(a)):
   z = a[i]
"""
Способ_3 = """
n = len(a)
i = 0
while i<n:
   z=a[i]
   i+=1
"""
Способ_4 = """
[x for x in a]
"""

Способ_5 = """
for i, item in enumerate(a):
       z=item
"""
Способ_6 = """
it = iter(a)
try:
   while True:
       z = next(it)
except StopIteration:
   pass
"""
sp1 = min(timeit.repeat(stmt=Способ_1, setup=setup, number = 1_000, repeat=5))
sp2 = min(timeit.repeat(stmt=Способ_2, setup=setup, number = 1_000, repeat=5))
sp3 = min(timeit.repeat(stmt=Способ_3, setup=setup, number = 1_000, repeat=5))
sp4 = min(timeit.repeat(stmt=Способ_4, setup=setup, number = 1_000, repeat=5))
sp5 = min(timeit.repeat(stmt=Способ_5, setup=setup, number = 1_000, repeat=5))
sp6 = min(timeit.repeat(stmt=Способ_6, setup=setup, number = 1_000, repeat=5))

print(f" Способ № 1 = {sp1:.4f}")
print(f" Способ № 2 = {sp2:.4f}")
print(f" Способ № 3 = {sp3:.4f}")
print(f" Способ № 4 = {sp4:.4f}")
print(f" Способ № 5 = {sp5:.4f}")
print(f" Способ № 6 = {sp6:.4f}")

Результаты:

Способ № 1 = 0.0994

Способ № 2 = 0.2813

Способ № 3 = 0.4848

Способ № 4 = 0.1188

Способ № 5 = 0.3090

Способ № 6 = 0.2196

Как видно из результата цикл for x in a работает намного быстрее, чем все остальные, на втором месте использование генератора for x in a, и самый медленный способ это цикл с while.

Пример. Определить число в списке, равное значению 5.

a =[1,2,3,4,5,6,7,8,9,0]

d = 5

 

 

Способ №1. Использование цикла for

for i in range ( len(a) ):
if a[i] == d:
     print(i, a[i])
     break
else:
   print ( "Число не найдено!"

# 4 5

 

Способ №2 Использование оператора вхождения in и метода index()

if d in a:
     print(a.index(d),d )
else:
   print ( "Число не найдено!" )

# 4 5

Способ №3 использование встроенной функции enumerate()

for i, item in enumerate(a):
   if item ==5:
        print(i, item)
       break
else:
   print("Число не найдено!")

# 4 5

  

Способ №4. Использование метода filter()

b = list(filter(lambda x: x == 5, a))
if b:
   print(a.index(*b),*b)
else:
   print("Элемент не найден.")

# 4 5

Способ №5. Использование цикла while и «барьерного» метода – выделяем дополнительный элемент списка – a[n] и заносим туда искомое значение. Это позволяет избавиться от проверки условия окончания цикла

a = [1,2,3,4,5,6,7,8,9,0,0]
d=5
n=10
a[n] = d
i=0
while (a[i]!=d):
     i=i+1
if i == n:
   print("Элемент не найден.")
else:
   print(i, a[i])

# 4 5

 

Способ №6. Использование метода index()

Индекс s.index(x) возвращает первое вхождение элемента x в последовательность s

print("индекс первого вхождения =", a.index(5))

# индекс первого вхождения = 4

 

Способ №7. Использование метода count()

Метод s.count(x)возвращает количество вхождений элементов x в последовательность s.

print("кол-во вхожденией", a.count(5))

   # кол-во вхождений 1

 

При выборе подходящего метода для поиска элементов в списках Python рекомендуется учитывать следующие факторы:

• Удобство использования: Некоторые методы, такие как цикл  for, оператор вхождения x in s и метод  index(), являются более простыми и понятными
• Гибкость: Некоторые методы позволяют выполнять дополнительные операции в процессе поиска, поэтому могут быть полезны такие методы, как  enumerate() или  filter()

Пример. Определить, есть ли в целочисленном списке четное число.

a =[1,2,3,4,5,6,7,8,9,0]

Все способы имеют временная сложность: O(n)

Способ № 1. Использование цикла for и range()

for i in range ( len(a) ):
if a[i]%2 == 0:
     print ( "Первое четное число =", a[i])
     break
else:
   print ( "Нет четных чисел!" )

Первое четное число = 2

Способ № 2. Использование цикла for и оператора in

for x in a:
if x % 2 == 0:
     print ( "Первое четное число =", x)
     break
else:
   print ( "Нет четных чисел!" )

Первое четное число = 2

 

Способ № 3. Использование генератора списка

b = [ x for x in a if x%2==0]
if b:
   print("Первое четное число =", b[0])
else:
   print("Нет четных чисел!")

Первое четное число = 2

 

Способ № 4. Использование функции enumerate()

for i, item in enumerate(a):
     if item %2==0:
       print( "Первое четное число =", item)
       break
else:
   print("Число не найдено!")

Первое четное число = 2

 

Способ № 5. Использование функции filter

b = list(filter(lambda x: x % 2 == 0, a))
if b:
   print("Первое четное число = ",b[0])
else:
   print("Элемент не найден.")

Первое четное число = 2