Стандарт не говорит и не должен указывать на сложность таких функций, как gethash.Представьте, если бы он это сделал: это ограничило бы реализации языка использованием реализаций функций, которые соответствовали сложности в стандарте.Если кто-то придумал гораздо лучшую функцию хеширования, то реализации не могли бы ее использовать.
Ну, вы могли бы поспорить, что это глупо: стандарту просто нужно указать верхние границы по сложности.Это позволило бы реализации использовать любую лучшую функцию, которая ей понравилась, верно?Но это также не ответ: могут быть (и во многих случаях) алгоритмы, которые имеют ужасную производительность в худшем случае, но гораздо лучше ожидаемой производительности.Чтобы справиться с этим в стандарте, было бы или невозможно (я думаю), или он был бы полностью покрыт сложными описаниями того, какая сложность была приемлемой, а когда и когда нет.
Предоставление верхних границ сложности также правилИз реализаций, которые хотели найти компромисс между (скажем) сложностью и масштабностью реализации и ее производительностью в некоторых случаях: реализация должна иметь разрешенные хеш-таблицы, которые, например, внутри alists: это обычно очень быстродля небольшого количества ключей, но их производительность падает для большого количества ключей.Такая реализация должна быть разрешена.
В некоторых случаях сложность вещей вроде очевидна из стандарта: кажется очевидным, что временная сложность length линейна вдлина списка (за исключением того, что он может не заканчиваться, если список является круглым).Но это не так: ничто не мешает реализации, поддерживающей где-либо значение длины, которое в некоторых случаях делает length постоянным временем.Это, очевидно, было бы героическим (на мой взгляд, неправдоподобным с точки зрения реализации) и бесполезной оптимизацией, но это не место стандарта, чтобы исключать это.
В качестве примера случая, когдаязык (не реализация CL!) делает что-то подобное, учитывая это описание предиката list? Ракета:
Возвращает #t, если v - это список: либопустой список или пара, вторым элементом которой является список.Эта процедура эффективно требует постоянного времени из-за внутреннего кэширования (так что любые необходимые обходы пар в принципе могут считаться дополнительными затратами на размещение пар).
Я не совсем понимаю, но яПодумайте, что Racket должен иметь в своем объекте cons флаг, который говорит вам, что его cdr является правильным списком, а затем полагается на неизменность, чтобы знать, что это всегда так, всегда верно.Если бы в CL была такая функция, было бы намного сложнее заставить ее работать в постоянном времени.