没有循环体的算法的复杂性是多少


for (int i = 0; i < n; i++) {
}

循环的主体中没有任何内容,但我仍然认为时间复杂性将是O(n)。这是真的吗?

是。

只要这个循环被执行(并且没有被编译器优化(,它确实是O(n(。这是因为循环迭代有一些开销,例如执行i++操作。

这确实是true(另请注意,正如@Berthur所指出的,循环是执行的,因此假设编译器没有优化(
即使正文是空的,您也在从i = 1迭代到i = nfor-loop带来了线性时间复杂性O(n)(注意空间复杂性O(1),假设您指定的for-loop是程序中唯一的一段代码(因此没有数组、映射等((

如果您的观点是实用的(实际程序执行的速度(,这取决于编译器和/或运行时系统。例如,Java编译器很可能会完全丢弃这段代码,因为从逻辑上讲,它什么都不做,而且不会花费任何时间。如果编译器没有进行任何优化,或者它遵循一个严格的约定,即即使没有效果,也必须执行代码,那么时间是线性的。如果代码由解释器执行,而不进行编译(尽管int暗示它是一种编译语言(,这同样取决于解释器的优化能力,但解释器通常不会进行太多优化,因此需要线性时间。

如果你的观点是理论性的,即算法理论作业,那么它通常不会被定义。这取决于机器模型是否考虑了可能的优化。

最新更新