返回声明的大O表示法？

Question

我是否正确地说大O符号的时间复杂度只是O(1)？

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

Answer 1

我是否正确地说大O符号的时间复杂度只是O(1)？

没有.

这是学生/学生之间的一种误解,我只能经常重复这一点:

大O符号是为了给复杂的东西,相对于一定的措施,对另一号码:

例如,说:

"就地FFT算法的空间要求为O(n),n为FFT二进制数"

说明了FFT在不同长度的FFT中所需的内存量.

所以,你没有指定

1. 你实际观察到的是什么？是从你的方法调用和返回之间的时间吗？仅仅是比较吗？在Java字节码指令或实际机器周期中测量"时间"吗？
2. 你有什么不同？您方法的调用次数？变量size？
3. 你真正想知道的是什么？

我想强调3:计算机科学专业的学生经常认为,如果他们只知道算法的理论时间复杂度,他们就会知道某些事情的表现.实际上,这些数字往往毫无意义.我的意思是.单次提取不在CPU高速缓存中的变量可能需要在CPU中添加100-10000的时间.如果直接编译,调用一个方法只是为了看某事是否为0将需要几十个指令,如果你使用的东西(半)解释为Java,可能会花费更多; 但是,在Java中,下次调用相同的方法时,它可能已经作为预编译的机器代码...

然后,如果您的编译器非常智能,它可能不仅内联函数,消除堆栈保存/恢复和调用/返回指令,甚至可能将结果合并到您在该返回值上调整的任何指令,这实质上意味着在极端情况下,此函数可能不会执行单个循环.

所以,无论你如何表达这一点,你都不能说"大O的时间复杂性是一种语言特定的功能",而不是说你的变化,以及你的平台究竟是什么.