Привет, я хочу знать, что такое временная сложность функции replaceAll для класса String, но я не могу найти никакой информации об этом. (http://docs.oracle.com/javase/6/docs/api/java/lang/String.html)
Не было бы лучше, чтобы Java включала сложности в Javadoc? Я считаю, что очень важно, чтобы кто-то знал.
Большинство функций имеют довольно простые сложности во времени. AFAIK, replaceAll - O (n)
ИМХО. Ничто не сравнится с тестированием этого эмпирически, например. с профилировщиком, поскольку весьма вероятно, что 99% используемых вами методов практически не влияют на производительность вашего приложения.
Сложность может быть задокументирована, если она будет гарантирована. Например, некоторые из требований к классу документов классов гарантируют. Например, из HashMap:
Эта реализация обеспечивает постоянную производительность для основных операций (get и put)...
Однако иногда сложность заключается в следующем:
javadocs API Java определяют общий контракт, который должен выполняться каждым методом, а не каким образом. Каждый разработчик API (скажем, OpenJDK, Oracle JDK и т.д.) Имеет определенную свободу в отношении того, как реализовать каждый контракт, и что свобода может включать в себя оптимизацию, даже жертвы в производительности. Таким образом, javadocs вообще не задают такие детали, как время/сложность функций, если это абсолютно необходимо для того, чтобы метод отвечал определенным требованиям к производительности.
Если вы используете пространственную/временную сложность основных операций для принятия проектных решений, вы почти наверняка ошибаетесь.
Сначала создайте правильное приложение, а затем профилируйте его. Затем оптимизируйте то, что раскрывает процесс профилирования как узкие места.
Общий ответ заключается в том, что сложность обычно зависит от факторов, которые слишком сложно анализировать. Это, безусловно, относится к String.replaceAll, где эффективная сложность критически зависит от строки regex. (Недостаточно спроектированное регулярное выражение может сделать совпадение медленным.)