m
Size: a a a
2020 April 09
IA
а как показать что сложность алгоритма действительно линейно зависит от длинны строки?
не обращаться наверное больше чем 1 раз к каждому элементу из строки
m
вот собсфтвенно бенчмарк это нагенерировать рандомных строк определенной длинны
m
и скормить их своей функции
и усреднить время работы
оно должно расти линейно с увеличением длинны строки и не зависеть от символов
и усреднить время работы
оно должно расти линейно с увеличением длинны строки и не зависеть от символов
m
не обращаться наверное больше чем 1 раз к каждому элементу из строки
это да
m
но если тебе например дают функцию и ты не знаешь что внутри
m
и тебе нужно проверить ее реальную сложность
что собственно и делают всякие one22
и прочие
что собственно и делают всякие one22
и прочие
P
А как впихнуть туда строки если она их не ест допустим
P
И как определяется сложность как с параметром временем обработки или витееватостью кода
m
И как определяется сложность как с параметром временем обработки или витееватостью кода
в том и суть что это не имеет значения
m
Вы просто запускаете функцию эту не зная как она работает с различными строками
m
и измеряете время за которое она дает ответ
m
и в среднем это время должно быть постоянным для строк длинной 5, например
независимо от того какие там символы
и быть в среднем в 2 раза больше для строк длинны 10
независимо от того какие там символы
и быть в среднем в 2 раза больше для строк длинны 10
m
вот тут импортится тестируемая функция и создается функция генерирующая рандомную строку заданной длинны
m
а вот тут мы для всех длин по очереди ее вызываем
m
ну там еще декоратор есть, но не суть)
m
принципиально тут ничего сложного - если должно для любых символов отрабатывать - значит нужно нагенерировать случайных символов строк и скормить