以下案例的复杂性是什么？

Question

假设我们有一个while循环，它基于一个真假条件进行迭代（假设一个队列是否为空）并且它内部有一个for循环：

while(!queue.isEmpty()) {
    // some lines of code
    for(int i = 0; i < n; i++) {
        // some code
    }
}

它会是O(n^2)还是O(n)。

编辑

 while(!queue.isEmpty()) {
        currNode = queue.remove();
        indexToSearch = currNode.data;
        for(i = 0; i < parentArr.length; i++) {
            if(parentArr[i] == indexToSearch) {
                newNode = new BinaryNode(i);
                if(!leftDone) {
                    currNode.left = newNode;
                    queue.add(newNode);
                    leftDone = true;
                } else {
                    currNode.right = newNode;
                    queue.add(newNode);
                    break;
                }
            }
        }
        leftDone = false;
    }

Answer 1

在这种情况下，您的复杂性取决于n和队列的大小。这样你的复杂性就是O（n * queue.size（））

（假设您的其他隐含代码行可以忽略）

为了确定“有用的”复杂性类，您需要包含所有可以改变您必须经历的迭代次数的参数。

（另外，既然你永远不会弹出你的队列，在最坏的情况下你会有一个不同的功能，但我想这暗示你在循环之前或之后弹出你的队列）

***********编辑****（看到代码后）

所以你有一个n值的数组。并希望构建一个具有n个节点的树

For each node you add: (meaning n times)
    You linearly search your array of values (worst case: you always need to search the entire array, also meaning n times)

所以你的复杂性是O（n ^ 2）

（如果您无法做出上述假设，那么您将获得其他复杂性，因为诸如“如果值不在队列中会怎么样”或'如果我的队列比数组大得多'会怎么样）