C语言 此代码片段的时间复杂度为 O(n)

Question

struct lists * list_depth[ht];
for(int i=0; i<ht; i++)
    list_depth[i]=NULL;
insert_to_list(&list_depth[0], root);
for( int i = 1; i < ht; i++ )
{
    struct lists * temp = list_depth[i-1];
    while( temp != NULL )
    {
        if(temp->node->llink!=NULL)
            insert_to_list(&list_depth[i],temp->node->llink);
        if(temp->node->rlink!=NULL)
            insert_to_list(&list_depth[i],temp->node->rlink);
        temp = temp->link;
    }
}

代码段的时间复杂度是多少？由于循环是嵌套的，它有 n^2 的复杂性吗？这是一个在二叉树的每个深度创建元素列表的程序。我认为是O(n(。我说的对吗？[N 是元素的数量]

Answer 1

不，这是 O(n * log(n((，因为你正在遍历树的长度，即 O(log(n((，n 次。