c - 使用 BST 对结构数组进行排序的函数的时间复杂度是多少？

Question

我有一个使用 BST 对数组进行排序的函数。首先，我使用 for 循环和函数插入创建树(在树中插入数据保持有序) 然后我按顺序访​​问树并在新的临时存档中以排序模式复制每个节点。 这是我的代码:

double btree_sort(SPerson Archive[], unsigned int ne, double    *btree_creating_time)
{
int i = 0;
TBinaryTree BinaryTree = NULL;

cont = 0;

LARGE_INTEGER freq;
LARGE_INTEGER t0, tF, tDiff;

QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&t0);
/*Algorithm*/
for (i = 0; i < ne; i++)       /*Creating B-Tree*/
    BinaryTree = binarytree_insert(BinaryTree, Archive[i]);
QueryPerformanceCounter(&tF);
tDiff.QuadPart = tF.QuadPart - t0.QuadPart;
*btree_creating_time = tDiff.QuadPart / (double)freq.QuadPart;
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&t0);
inorder(BinaryTree, Archive);
/*end*/
QueryPerformanceCounter(&tF);
tDiff.QuadPart = tF.QuadPart - t0.QuadPart;

free(BinaryTree);
return tDiff.QuadPart / (double)freq.QuadPart;
}

int  inorder(TBinaryTree BinaryTree, SPerson Archive[])
{
if (BinaryTree)
{
    inorder(BinaryTree->left,Archive);  

    swap(&Archive[cont++], &BinaryTree->information);

    inorder(BinaryTree->right, Archive);

}                  
return 1;
}

 TBinaryTree binarytree_insert(TBinaryTree bt, SPerson to_add)
{
if (bt == NULL)   
{
    TNode *new_node = create_node(to_add);
    if (new_node == NULL) 
    {
        MessageBoxA(0, "Error allocating memory.", "", 0);
        exit(1);
    }
    return new_node;
}
else
{
    if (strcmp(to_add.id, bt->information.id)<0)
    {
        bt->left = binarytree_insert(bt->left, to_add);
        return bt;    
    }
    else
    {
        bt->right = binarytree_insert(bt->right, to_add);
        return bt;  
    }
}
}

考虑一下:

1. 插入 B 树的时间复杂度在最好情况下为 Θ(1)，在最坏情况下为 Θ(nlogn)。 (无论如何写 Θ 是正确的还是我应该说 O 最好的情况和 Ω 最坏的情况？)

2. 有序访问的时间复杂度为 Θ(n)

因此在树中插入 n 个元素、访问和交换的时间复杂度为:

最佳情况:[只有一个元素] Θ(1) + [Θ(1) + Θ(4)] [交换函数时间复杂度]

最坏情况:Θ(nlogn) + [Θ(n) + Θ(4)]

我说的对吗？有什么建议吗？提前致谢。

Answer 1

最坏情况下的复杂性称为 O - Big Oh 表示法。我们通常只使用最坏情况的复杂度。此外，在 Btree 中插入所有节点的时间复杂度为 O(nlogn)。所以对一棵树进行排序就是插入所有的键，然后按顺序遍历这棵树，其复杂度为 O(n)。

所以整体复杂度是 O(nlogn) + O(n) 即 O(nlogn)