Что значит O(1)?

Question

[Vladimir Onokhov]

Искал в интернете, но так и не понял...

Comments

[WbICHA]

Оценка сложности алгоритмов.

Answer 1

[Wataru]

Время работы алгоритма - константа. Т.е. не зависит от размера входных данных (или их нет вообще)

Answer 2

[0ralo]

Сложность алгоритма + и еще

Answer 3

[mayton2019]

Тут - проще объяснить применительно к конкретным языкам разработки и технологиями. Например время доступа к элементу хеш таблицы Java (HashMap) оценивается как O(1). Тоесть время всегда постоянное и не зависит от прочих условия типа размера таблицы. А если у нас вместо хеш-таблицы - красно-черное дерево (TreeMap) - то тогда время доступа оценивается как O(log n). Тоесть логарифмически зависит от размера данных в дереве.

Считается что O(1) лучше чем O(log n). Но этот тезис действует на объеме данных близком к бесконечности. На малых объемах структуры - неразличимы или могут менять свои свойства в зависимости от разных начальных условий (были ли в кеше L1/L2/L3 до этого уже прочитанные данные).

Comments

[Jacen11]

Например время доступа к элементу хеш таблицы Java (HashMap) оценивается как O(1).

что за бред. HashMap это не просто хеш таблица. Это к бакету доступ за O(1). А внутри бакета доступ O(n), либо O(log n). То есть доступ к элементу точно не может быть константным, если мы берем худший вариант.

[Vladimir Onokhov]

время всегда постоянное и не зависит от прочих условия

спасибо, этого я и ожидал

[mayton2019]

Jacen11, да. Вся литература по хеш-таблицам оперирует именно таким определением O(1) для хеш-таблиц. Ситуация промаха мимо ключа которую вы описываете - достаточно редкая. И я не просто так говорил о Java-реализации HashMap. В дефолтном конструкторе (99% которого используется) таблица создается с коэффициентом заполнения 0.75. А при такой пропорции ключей и бакетов вероятность коллизии очень мала. Поэтому вашу формулу O(1) или O(n) здесь нужно применять с сильной поправкой на теор-вер. А теор-вер там уже во много раз сложнее и проще его не вычислять а доказывать практически. Тоесть просто симуляцией работы хеш-таблицы.

Разумеется мои рассуждения адресованы Вам а не автору. Ему это можно пропустить т.к. обычно на собеседовании когда говорят о O(n) не копают каждую структуру данных. Нет времени на это.

Ну а вы - изучайте для себя структуры данных Java. Это полезно.

[Jacen11]

mayton2019,

Вся литература по хеш-таблицам оперирует именно таким определением O(1) для хеш-таблиц

я в курсе. Только вы не про хеш таблицы говорили, а про хешМапу

Ситуация промаха мимо ключа которую вы описываете - достаточно редкая.

без разницы какая вероятность, раз вы не в курсе, указывают худший случай всегда

здесь нужно применять с сильной поправкой на теор-вер.

еще раз, никто так не делает, всегда оценивают худший случай

собеседовании когда говорят о O(n) не копают каждую структуру данных

не говорят так. Это абсолютно не правильный ответ для хешмапы, она работает сложнее и в разных версиях по разному

Ну а вы - изучайте для себя структуры данных Java. Это полезно.

я то уже изучил, а вы кажется не очень

[mayton2019]

я в курсе. Только вы не про хеш таблицы говорили, а про хешМапу

Я понял. Вы просто не в курсе. В Java - HashTable и HashMap это одно и тоже.

Я не просто так акцентировал.