空algorithmO（0）的时间复杂度是多less？
所以给了以下程序：
这个程序的时间复杂度是O（0）吗？ 换句话说，是0 O（0）？
我想在另外一个问题上回答这个问题会让我们看到这个问题 。
编辑：很多好的答案在这里！ 我们都同意0是O（1）。 问题是，也是0 O（0）？
维基百科 ：
用大O表示法描述函数通常只提供函数增长率的上限。
从这个描述中，由于空algorithm需要0次执行，所以它具有O（0）的上界性能。 这意味着，这也是O（1），这恰好是一个更大的上界。
编辑 ：
从CLR更正式（1ed，第26页）：
对于给定的函数g （ n ），我们表示O （ g （ n ））这个函数集合
O （ g （ n ））= { f （ n ）：存在正常数c和n 0 ，使得对于所有n≥n0，0≤f （ n ） ≤cg （ n ）
因此，无论input如何，在0时间内执行的空algorithm的渐近时间性能都是O （0）的成员。
编辑2 ：
我们都同意0是O（1）。 问题是，也是0 O（0）？
根据定义，我说是的。
此外，我认为这个问题比许多答案显示的更重要。 空algorithm本身可能是没有意义的。 但是，每当指定一个非平凡的algorithm时，空algorithm可以被认为是位于指定algorithm的连续步骤之间以及在algorithm步骤之前和之后。 很高兴知道“虚无”不影响algorithm的渐近时间性能。
编辑3 ：
Adam Crume提出以下要求 ：
对于任何函数f （ x ）， f （ x ）都在O（ f （ x ））中。
certificate：设S是R的子集， T是R * （非负实数）的一个子集，设f （ x ）： S → T且c≥1。则0≤f（ x ）≤f （ x ）对于所有x∈S导致0≤f（ x ）≤fc（ x ）。 因此f （ x ）∈O（ f （ x ））。
具体来说，如果f （ x ）= 0，那么f （ x ）∈O（0）。
无论input如何，都需要相同的时间才能运行，因此定义为O（1）。
有几个答案认为复杂度是O（1），因为时间是一个常数，时间是由一些系数和1的乘积界定的。那么，时间是一个常数并且是有界的，这并不意味着最好的答案是O（1）。
考虑一个以线性时间运行的algorithm。 通常被指定为O（n），但是玩魔鬼的拥护者。 时间以一定的系数和n ^ 2的乘积为界。 如果我们把O（n ^ 2）看成一个集合，那么复杂度足够小的所有algorithm的集合都是线性algorithm。 但这并不意味着最好的答案是O（n ^ 2）。
空algorithm在O（n ^ 2）和O（n）以及O（1）和O（0）中。 我投O（0）。
对于空algorithmO（0），我有一个非常简单的参数：对于任何函数f（x），f（x）都在O（f（x））中。 简单地让f（x）= 0，并且我们有0（空algorithm的运行时间）在O（0）中。
在附注中，当人们写f（x）= O（g（x））时，我讨厌它，当它应该是f（x）∈O（g（x））。
大O是渐近表示法。 要使用大O，你需要一个函数 – 换句话说，expression式必须用n来参数化，即使不使用n也是如此。 说数字5是O（n）是常数函数f（n）= 5是O（n）是没有意义的。
所以，要分析大O的时间复杂度，你需要一个n的函数。 你的algorithm总是可以做0步，但没有一个变化的参数谈论渐近行为是没有意义的。 假定你的algorithm是由n来参数化的。 只有现在你可以使用渐近符号。 如果你不指定什么是n（或者隐藏在O（1）中的variables），那么说它是O（n 2 ），甚至O（1）是没有意义的！
一旦你决定了步数，它就是大O定义的问题：函数f（n）= 0是O（0）。
由于这是一个低级问题，它取决于计算模型。 在“理想主义”假设下，你可能什么都不做。 但是在Python中，你不能说def f(x): def f(x): pass但是只有def f(x): pass 。 如果你假设每一条指令，即使pass （NOP），都需要时间，那么对于某个常数c，复杂度就是f（n）= c，除非c != 0你只能说f是O（1），而不是O（0）。
值得注意的是大O本身与algorithm没有任何关系。 例如，当讨论泰勒展开时，你可以说sin x = x + O（x 3 ）。 另外，O（1）并不意味着不变，它意味着以常量为界。
到目前为止所有的答案都解决了这个问题，好像有一个正确的答案和一个错误的答案。 但是没有。 问题是一个定义问题。 通常在复杂性理论中，时间成本是一个整数 – 虽然这也只是一个定义。 您可以自由地说，立即退出的空algorithm需要0个时间步或1个时间步。 这是一个抽象的问题，因为时间复杂性是一个抽象的定义。 在现实世界中，你甚至没有时间步骤，你有连续的物理时间; 可能是一个CPU有时钟周期，但是一台并行计算机很容易有asynchronous时钟，并且在任何情况下，一个时钟周期是非常小的。
这就是说，我认为说停止操作需要1个时间步骤，而不是0个时间步骤更为合理。 这似乎更现实。 对于许多情况来说，它可以说是非常保守的，因为初始化的开销通常远远大于执行一个算术或逻辑操作。 给空algorithm0时间步骤只是合理的build模，例如，一个函数调用被优化编译器删除，知道该函数不会做任何事情。
应该是O（1）。 系数总是1。
考虑：
如果某事长得像5n，你不会说O（5n），你说O（n）[换句话说，O（1n）]
如果像7n ^ 2那样增长，你不会说O（7n ^ 2），你说O（n ^ 2）[换句话说，O（1n ^ 2）]
同样，你应该说O（1），而不是O（其他常数）
没有O(0)这样的东西。 即使是一台oracle机器或一台超级计算机，也需要一次操作的时间，即solve(the_goldbach_conjecture) ，ergo：
所有机器，理论或实际，有限或无限产生algorithm，最小时间复杂度为O(1) 。
但是再次，这里的代码是O(0) ：
// Hello world!
🙂
从定义上来说，我认为它是O（1），但是如果你想得到技术上的话就是O（0）：因为任何常数O（k 1 g（n））等于O（k 2 g（n）） （1 * 1）相当于O（0 * 1），所以O（0）相当于O（1）。
但是 ，空algorithm不像例如身份函数，其定义类似于“返回您的input”。 空的algorithm更像是一个空的语句，或者两个语句之间发生的任何事情。 它的定义是“对你的input完全没有任何影响”，据推测甚至没有简单的input的隐含开销。
因此，空algorithm的复杂性是独一无二的，因为O（0）的复杂度是任意函数的零倍，或者仅仅是零。 因此，由于整个业务如此古怪，而且由于O（0）并不意味着有用的东西，因为即使讨论这样的事情也有些荒谬，O（0）的一个合理的特例就是这样的：
空algorithm的复杂性在时间和空间上是O（0）。 时间复杂度为O（0）的algorithm相当于空algorithm。
所以你去了
鉴于大O的正式定义：
设f（x）和g（x）是在实数集上定义的两个函数。 然后，我们写：
当x接近无穷大时， f(x) = O(g(x))如果存在实数M和实数x0，则：
|f(x)| <= M * |g(x)| for every x > x0
正如我所看到的，如果我们用g（x）= 0（为了有一个复杂度为O（0）的程序），我们必须有：
|f(x)| <= 0 |f(x)| <= 0 ，对于每一个x> x0（这里实际存在的实际M和x0的约束）
这只有当f（x）= 0时才是正确的。
所以我会说，不仅空的程序是O（0），而且是唯一的程序。 直观地说，这应该是真实的，因为O（1）包含所有需要恒定步数的algorithm，而不pipe其任务的大小，包括0。 它已经在O（1）。 我怀疑它纯粹是出于简单的定义，我们使用O(1) ，它也可能是O(c)或类似的东西。
对于所有函数f，0 = O（f），因为0 <= | f |，所以它也是O（0）。
O（1）意味着algorithm的时间复杂度总是不变的。
假设我们有这个algorithm（用C）：
void doSomething(int[] n) { int x = n[0]; // This line is accessing an array position, so it is time consuming. int y = n[1]; // Same here. return x + y; }
我忽略了数组可能less于2个位置的事实，只是为了保持简单。
如果我们计算两条最昂贵的线路，那么总共有2条线路。
2 = O（1），因为：
2 <= c * 1，如果c = 2，则对于每个n> 1
如果我们有这个代码：
public void doNothing(){}
我们把它算作有0条膨胀线，说它有O（0）O（1）或O（1000）没有区别，因为对于这些函数中的每一个，我们都可以certificate同样的定理。
通常，如果algorithm需要一个不变的步骤来完成，我们说它有O（1）的时间复杂度。
我想这只是一个约定，因为你可以使用任何常数来表示O（）中的函数。
按照惯例，它是O（c），只要你不依赖于input大小，其中c是任何正的常数（通常使用1 – O（1）= O（12.37））。
