CD
Что приборы?
в восьми пачках беломора О(1) сигарет
Size: a a a
2020 August 29
V🇺
Что приборы?
поиск подстроки в строке константного размера - тоже константа
IZ
поиск подстроки в строке константного размера - тоже константа
Ладно, может я не так понял задачу...
IZ
поиск подстроки в строке константного размера - тоже константа
Строка всегда константного размера, но её размер то - N !
V🇺
Строка всегда константного размера, но её размер то - N !
в данном случае - размер строки 200, а не N
IZ
если N ограничен то O(N)=O(1)
N всегда ограничен, тем не менее сложность линейная.
Ты должен измерять алгоритм в количестве сравнений символов
Ты должен измерять алгоритм в количестве сравнений символов
IZ
в данном случае - размер строки 200, а не N
Ну и что?
CD
N всегда ограничен, тем не менее сложность линейная.
Ты должен измерять алгоритм в количестве сравнений символов
Ты должен измерять алгоритм в количестве сравнений символов
Ниет, Илья. Минимум из N и 200 это константа, никаких N
IZ
Ниет, Илья. Минимум из N и 200 это константа, никаких N
Ну и что что константа?
CD
Ну и что что константа?
Значит, время работы программы теперь не превышает какого-то не зависящего от N параметра
IZ
Ниет, Илья. Минимум из N и 200 это константа, никаких N
Лучше расскажите мне что такое
S[:200]
S[:200]
IZ
Значит, время работы программы теперь не превышает какого-то не зависящего от N параметра
Да с чего?
IZ
Значит, время работы программы теперь не превышает какого-то не зависящего от N параметра
Вас так сбило, что две переменные назвали N?
CD
Да с чего?
Ну сколько N не расти, все равно 200, а первые 200 нас все равно не волнуют, асимптотика
IZ
Ну сколько N не расти, все равно 200, а первые 200 нас все равно не волнуют, асимптотика
Это согласен, но поиск то не бесплатный.
IZ
Ну сколько N не расти, все равно 200, а первые 200 нас все равно не волнуют, асимптотика
Ладно, я понял вашу идею, это действительно верное рассуждение
CD
Это согласен, но поиск то не бесплатный.
Не бесплатный, но подстрок длиннее входной не бывает, так что там тоже не больше 200. В 40к операций наша программа совершенно точно уложится, какое бы там ни было N
V🇺
Это согласен, но поиск то не бесплатный.
асимптотически - бесплатный
IZ
олсо, на icfpc в этом году выяснили же, что питон - лучший?
Ага питон лучший!
Но меееедленный....
Но меееедленный....
CD
асимптотически - бесплатный
Интересно, алгоритм за О(1) с официально худшей константой есть? Надо бы конкурс