March 20th, 2017

404

сложность

Скажите, математики, а как качественно различаются функции, у которых сложность различается в тысячу раз? Допустим, у нас есть два алгоритма по угадыванию пароля (pin'а). Один угадывает со второй попытки и, редко, с третьей, а другой алгоритм в среднем с пятисотой, но иногда - с тысячной.

С точки зрения математика и o(n) нотации, эти функции одного класса. Но мы точно видим, что одно - это "ой-ой-ой feasible attack на кредитные карты", а другое - глупость и не интересно.