时间戳

首页 > 解决方案 > If 语句和 O(1) 复杂度

java - If 语句和 O(1) 复杂度

问题描述

如果存在 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() 是默认的；我没有创建（覆盖）一个。

标签： javaif-statementcomplexity-theory

解决方案

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

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

换句话说，30次O(1)操作、50O(1)次操作和 100 次O(1)操作都是静止的O(1)。但是，99 次O(1)操作和一次O(n)操​​作是O(n).

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

推荐阅读