我们平常写的 C++ 程序,都有一定的时间复杂度,它们通常都不会太小。但是,时间复杂度最小可以达到多少呢?带着这个疑问,我写了如下代码:
int main(){}
“这就是最短的能通过编译的 C++ 代码了,它的用时应该只包含 return 0 的用时吧!”我想。但是,当它开始运行后,我才看到了这代码的真面目。当我在 Windows 7 电脑上,用 Dev-C++ 编译完一遍,控制台显示出来时,它竟突然“犹豫”了,连平常闪烁的光标也无影无踪了。过了 0.5s,它好像才反应过来似的,宣告了程序结束。我又试了好几次,虽然有时程序只有 50∼100ms 延迟,可有时,程序仍然会犯“拖延症”,愣了 0.5s 才结束程序。我又将 Dev-C++ 中的最高级优化打开(不知道是什么优化,也许是 O3),虽然程序较快结束的几率大了些,但仍有延迟 >100ms 的情况零星出现。
难道时间复杂度最小也只能这样,有着无法解决的随机延迟吗?那为什么评测机判定的程序用时却最低可达 0ms?这是因为 Dev-C++,电脑,还是程序的问题?