关于大O符号的问题

Question

假设我有 getNumber() return 我在 class 中存储了一个整数，我在 main.

中实例化了它

public int getNumber()
{
  return number;
}

上面的代码会采用 O(1) 而下面的代码会采用 O(2) 吗？还是我误解了 O 表示法是如何根据 CPU 周期来完成操作的？

public int getNumber()
{
  int myNumber = number;
  return myNumber;
}

所以重新表述我的问题，在一行中 returning 一个对象的变量与声明另一个变量来保存该对象的变量然后在另一行中 returning 它在性能方面是否相同？

Answer 1

Big-O 符号不是关于计算 CPU 周期的确切数量，而是关于计算与某些不同大小（例如，输入的长度）相关的数量级。这里，两个函数都有一个不依赖于任何额外大小的恒定运行时间，因此都是 O(1)。

（顺便说一下，在任何 real-world 场景中，我希望一个像样的编译器内联 int myNumber = number 行，并使两个函数声明基本相同）

Answer 2

首先：大O表示法是对函数的分类，符号O(n)代表集合从 ℝ 到 ℝ 的所有函数最多增长 fast/much 作为函数 f(n) = n 的任何正倍数。

此技术介绍（已缩小到此上下文）对于阐明大 O 表示法用于说明 fast/much 函数如何增长是必要的。
在这样做时，我们不考虑确切的倍数：10n、5n 和 20n 全部是 O(n) 因为它们是函数 n.
的倍数虽然像 O(5n) 这样的东西有点滥用符号（我们有多个符号表示与 O(n) 相同的集合），但它们经常被使用。

大O符号需要一个函数来衡量，在计算复杂度理论中两个主要的函数衡量是时间复杂度和[=99] =]复杂度。

时间复杂度是一个函数，它衡量算法产生其输出所花费的步数，作为长度的函数其输入的编码（即输入10为长度2，两位数）。
这里有一个隐藏的问题，什么是 step?
该步骤仅在给定计算模型时才是一个步骤，换句话说，首先需要确定计算是如何完成的，哪些步骤是可能的。
文献中很少明确或明确说明这一点，我不知道为什么。

例如指令a = b + c经常被认为是单步，这是因为使用的计算模型是编写程序的high-level语言。
然而，在某些上下文中 a = b + c 不被视为单个步骤，其中一个上下文是 bit-complexity，该模型将每个位的每个操作都视为单个步骤（因此该指令将是 O(m)，其中 m 是数字的长度，以位为单位）。

在您的示例中，第一个实现具有复杂性 O(1)，因为函数体中只有一条语句。
第二个有两条语句，其中一条是变量初始化。由计算模型来设置从常量表达式初始化的变量（注意它们是否从必须在运行时计算的东西中获取值）是否算作一个步骤。
你可以放心地假设他们总是这样做，因为他们最多增加 O(1) 到总成本，这将由函数体中的任何代码支配（除非函数体只有变量初始化）。
因此，第二个函数的成本为 O(2)（滥用符号），但根据定义为 O(2) = O(1)。

这应该澄清对 CPU 周期的误解。当使用 high-level 语言描述我们不关心 CPU 循环的算法时，我们的计算模型是一台直接理解 high-level 语言的机器！一定是这种情况，因为我们不知道它将如何翻译成汇编指令，所以我们无法计算 CPU 个周期。
记住 time 复杂度 not 关于我们测量的时间，它是关于 steps 的数量而不是关于经过的滴答数。
当使用 high-level 语言时，隐含的计算模型是语言的每个语句都是一个步骤的模型。

还有一点要注意：时间复杂度结合大 O 表示法不能过于严密地用来衡量性能。具有小常数的 O(n^2) 优于具有如此大常数的 O(n)，对于问题的任何实际实例，它总是大于 n 的任何可能值。
但这是一个麻烦（主要在数值方法中发现），因为可以删除一般概述常量。事实上，它是一个很棒的工具，否则分析会太复杂。

关于大O符号的问题

Queston about big O notation

time

big-o

cpu

notation