Python. Простые алгоритмы
Рассматриваются алгоритмы линейной обработки списков, строк - это последовательный поиск и нахождение заданного значения, когда нужно просмотреть все элементы с первого до последнего. Как только будет найден элемент, равный заданному значению, необходимо вывести найденное значение и завершить поиск. Такой алгоритм является простейшим алгоритмом поиска. Сложность поиска O(n).
В программировании «О» большое описывает наихудший сценарий. Допустим, у нас есть массив чисел, где мы должны найти какое-то определенное число при помощи цикла for. Оно может быть найдено при любой итерации, и чем раньше, тем быстрее функция завершит работу. О-нотация всегда указывает на верхнюю границу, т. е., описывает случай, когда алгоритму придется осуществить максимальное количество итераций, чтобы найти искомое число. Как, например, в том случае, если это число окажется последним в перебираемом массиве
Строка состоит из символов латинского алфавита A, B, C. Найдите длину самой длинной подцепочки, состоящей из символов C
Исходная строка
s ='CCCBACCBCCCCCACCABCACCACCCCAAABAABBBCCCCBCCCCBBBCBCBACCACCABCACCBBBBCACBCCCCCAC'
Способ № 1 Использование цикла for
cur = mx = '' #текущая и макс длина
for x in s:
if x=='C':
cur += "C"
mx = max(cur, mx, key=len)
else:
cur=''
print(mx,len(mx))
# CCCCC 5
Временная сложность: O (n)
Способ № 2 Использование метода replace()
s = s.replace('A',' ').replace('B', ' ')
mx = max(s.split(' '), key=len)
print(mx,len(mx))
# CCCCC 5
Временная сложность: O (n)
