Замечание Big O только о возвращении?

Question

Правильно ли я говорю, что сложность времени в большой записи O будет только O (1)?

public boolean size() { 
     return (size == 0); 
    } 

Answer 1

я прав, говоря, что временная сложность в большой нотации O бы только O (1)?

No.

Это настолько распространено заблуждение среди студентов/учеников, что я могу только постоянно повторять это:

Big-O обозначение, чтобы дать сложность из что-то, с уважение к определенным мерам, над другим номером:

Например, говоря:

«Алгоритм в месте FFT имеет потребность в пространстве О (п), с п-число FFT бункеров»

говорит что-то о том, сколько FFT будет нуждаться в память, наблюдаемая для разных длины БПФ.

Таким образом, вы не указали

1. Что вещь вы на самом деле наблюдения? Это время между вызовом и возвратом из вашего метода? Это только сравнение? Является ли «время» измерено в инструкциях байт-кода Java или реальных машинных циклах?
2. Что вы будете менять? Количество вызовов вашего метода? Переменная size?
3. Что это такое, что вы на самом деле хотите знать?

Я хотел бы подчеркнуть, что 3: студенты-информатики часто думают, что они знают, как что-то будет вести себя, если они просто знают теоретическую сложность времени алгоритма. В действительности эти цифры имеют тенденцию иметь значение ничего. И я имею в виду это. Единая выборка переменной, которая не находится в кэше CPU, может занять 100-10000 дополнений в CPU. Вызов метода только для того, чтобы увидеть, будет ли что-то 0, потребуется несколько десятков инструкций, если они скомпилированы напрямую, и может потребоваться намного больше, если вы используете что-то, что (semi-) интерпретируется как Java; однако, в Java, в следующий раз, когда вы вызовете тот же самый метод, он уже может быть там как предварительно скомпилированный машинный код ...

Тогда, если ваш компилятор очень умный, он может не только встроить функцию, удалив стек сохранения/восстановления и вызова/возврата, но, возможно, даже слияния результата с любыми инструкциями, которые вы настраивали на этом возвращаемом значении, что по сути означает, что эта функция в крайнем случае может не выполнять один цикл для выполнения.

Так что, независимо от того, как вы это положили, вы не можете сказать«сложность времени в большом O того, что является спецификой для языка», не говоря о том, что вы меняете, и точно, что такое ваша платформа.