If 语句和 O(1) 复杂度

Question

如果有一个 if else 条件并且 if 由 2 行组成，else 由 1 行组成，或者通常情况下还有一行，程序是 O(1) 吗？

edit1: 下面的例子是关于链表的。

例如：

    public String smth() throws NoSuchElementException{
        if (size!=0) {  
            Object n = tail.item;
            
            if (size!=1) {
                tail = tail.prev;
                tail.next = null;
                
            }
            else{       
                head.prev = null;       
                head = head.next;
                tail = tail.prev;
            
                
            }   
            
            this.size = this.size - 1;
            return n.toString();
        }else {
            throw new NoSuchElementException();
        }
    }

编辑2：

谢谢大家的建议。 toString() 是默认的；我没有创建（覆盖）一个。

Answer 1

虽然这两个指标往往与整体性能相关（因为“做更多事情”的程序通常需要更长的时间才能达到运行），但代码行数和计算复杂性衡量的不是同一件事。

澄清一下，说一个程序的复杂度是 O(1) 只是意味着无论输入的大小如何，它都需要恒定的步骤数。添加更多代码行本身并不会改变计算复杂性（除非其中一行正在做比 O(1) 更复杂的事情）。

换句话说，30次O(1)次操作，50次O(1)次操作，100次O(1)次操作，都还是O(1)次。然而，99 O(1) 次操作和一次 O(n) 次操作是 O(n).

也就是说：请务必检查 n.toString() 行。我对它实际包含的内容没有太多了解，但它可能是 O(n) 取决于它的实现方式。如果该行是O(n)，它会使整个方法O(n)；否则，除非我遗漏了什么，否则除了 O(1) 之外，我看不到任何东西。（另外，我承认我不记得在 Java 中抛出异常的计算复杂性，这是我必须做更多研究的事情）。

Answer 2

O(x)指的是下面的概念。但首先，提示：提示：你不能在不实际解释 n 是什么的情况下说“这个算法是 O(n^2)”。它很少被提及，因为它从上下文中往往很明显，但它仍然是一个完全没有意义的陈述，没有锁定 O(x) 描述中使用的变量所代表的内容。即使 O(1) 也没有意义，除非您枚举 'variable(s)' （它不必是方法中的文字参数或变量）它是 O(1) for.

制作折线图。在 x 轴上，输入 'n'。无论 n 可能是什么（见上面的提示）。然后，在 y 轴上，输入 'time taken by computer to calculate it'.

当您开始时（低 n），这些图表往往 到处都是，因为您更多地测量随机机会，无论您的 winamp 接管CPU 核心暂时解码一些更多的 mp3，等等。但是，只要您移动到 'right'（高 n 值）足够远，曲线就会稳定下来并变成可识别的东西。

O(1) 算法将稳定为 水平线 （因为如果绘制 y = 1，它就是水平线）。例如，假设我们看一下操作：“使用 .get(k) 方法在 Map<Integer, String> 中检索与键关联的值”。显然，'n' 因此是：该地图的大小。

所以，让我们开始吧！让我们编写一段从 1 到 1 亿循环的简单代码，每次循环，它都会创建一个新的哈希图，将那么多键放入其中，然后启动秒表，然后运行s a .get()操作，然后结束秒表。然后我们绘制*.

对于 java 中的大多数地图实现，曲线最终看起来像一条水平线： .get() 操作所花费的时间量没有变化，地图是否有 5条目，或 5000 万个 em。

对于某些（例如 TreeMap），曲线稳定为看起来像 y = log x 的曲线。这是一条缓慢增长的线，但是非常、非常、非常缓慢，并且随着它的增长，速度越来越慢。

最终的 'settles down into' 曲线？ THAT 是 O(nlogn) 的意思：曲线最终稳定下来，大致类似于绘制公式 y = x * log(x).

这也是为什么您从不说某些算法是 O(5*n^2 + n) 的原因 - 因为这条曲线，一旦您越过起始位，看起来就像 O(n^2) 一样。

所以，回到您的问题：'n' 是关于什么的？如果 n 大约是 'size of linkedlist'，那么无论您的链表有多大，您的算法显然都会执行相同的步骤。因此它相对于 'size of list' 是 O(1)。假设（这有点奇怪，因为它与列表实现没有关系），但是如果您将 'n' 定义为：“内部对象具有的字段数”，并且您的 toString impl 遍历所有字段打印它们，那么它将是 O(n)。这不是一个有用的区别（你的 list impl 与它存储的东西的 toString impl 无关，所以我们为什么要通过引入它来混淆事物？），但它表明你无法回答什么算法的性能特征无需首先解释您拥有哪些变量。

你可以有多个；例如，在以下操作中：“给定一个作为字符串的正则表达式，然后是一个输入字符串，Thompson/NFA 算法需要多长时间才能将输入与正则表达式匹配？”答案通常为“O(n+m)，其中 n 是正则表达式的大小，m 是输入字符串的大小”。

*) 这真的不是那么容易，你必须运行大量的 get 操作并获得平均值，不过有像 JMH 这样的框架可以做到这一点。

If 语句和 O(1) 复杂度

If statement and O(1) complexity

java

if-statement

complexity-theory