确定复杂性等级

这里的大标记是什么？一个解释将不胜感激。谢谢。确定复杂性等级

public static int[] mystery1(int[] list) { 

    int[] result = new int[2 * list.length]; 
    for (int i = 0; i < list.length; i++) { 
    result[2 * i] = list[i]/2 + list[i] % 2; 
    result[2 * i + 1] = list[i]/2; 
    } 

    return result; 

}

来源

2013-02-08 cluv

是功课吗？ – 2013-02-08 20:43:01

本地化太大.. – Puppy 2013-02-08 20:44:17

它是O(n)，其中n是列表的长度。无论如何你都要经历整个列表。

算术运算的数量：

2N次乘法
2N增加
2N divitions
ň模运算

这还不算算术运算实现for循环。

来源

2013-02-08 20:37:50 user000001

为O（n）

命令的量不是作为控制结构（循环）使用如此重要。如果你考虑这个函数，它只有一个循环。该循环使用列表（n）的长度作为迭代次数。如果列表长度加倍，循环完成所需的时间也会增加。

来源

2013-02-08 20:39:04 Grambot

嗯，它不仅是循环。你还必须考虑你正在使用的非原始操作（尤其是递归调用）（尤其是递归对于估计复杂度有时会有点痛苦）。 – Cubic 2013-02-08 20:41:16

好的一点，任何允许程序流程去除A-> B的任何地方都有可能增加函数/算法操作的复杂度。 – Grambot 2013-02-08 21:46:29

大O表示最坏的情况。由于无法比较两台不同计算机执行操作所需的时间，因此Big O适用于算法执行的操作次数。操作可以是从方法调用到变量赋值的任何操作。

经历代码

int[] result = new int[2 * list.length]; 
    for (int i = 0; i < list.length; i++) { 
    result[2 * i] = list[i]/2 + list[i] % 2; 
    result[2 * i + 1] = list[i]/2; 
    } 

    return result;

重负载处于for循环。因为你循环list.length次，你这个方法的大O是O(list.length)。但是，为了彻底，您还可以进行其他操作。当你分配一个新的int数组时，你可以计算它。当您计算result数组中的索引2 * i时，您也可以这样计算。但是，由于这些操作需要一段时间，所以它们会在循环所需的可变时间内被吞并。

你应该阅读笔记，但你会学到，也有不同程度的复杂性，恒定的，线性的，对数的，等等

来源

2013-02-08 20:40:16

“大O代表最坏的情况。”不是真的。这是运行时渐近行为与输入长度的近似值。形式上大O意味着一个上限，尽管在通俗用法中它通常意味着“上限和下限”。 – Cubic 2013-02-08 20:43:36

对我来说，一个上限是最差的（时间，比方说）。 – 2013-02-08 20:45:21

@Cubic是不是下限的小o？ – user000001 2013-02-08 20:46:10

这是O（n）。因为循环迭代只有一个。这取决于阵列的长度并将线性增长。

来源

2013-02-08 21:02:08

确定复杂性等级

回答

相关问题