c++ - 使用排序数组实现集合

Question

这是一个数据结构问题，但也与实现有关。集合通常使用 BST 实现，但我的教授希望我们知道如何在仅提供有限选项时实现某些数据结构。所以他希望我们能够理解如何只使用一个数组来创建一个集合。

使用标准(未排序)数组，我了解实现/复杂性...

void add(Student[] arr, Student findstu)
{
    Student stu = new Student();
    int i=0;
    boolean found = false;
    while(stu!=NULL)
    {
        stu = arr[i++];
        if (stu==findstu)
        {
             found = true;
        }
     }
    if (found==false)
    {
         arr[i+1] = findstu;
    }
 }

添加/删除/包含几乎是相同的代码，都将有第一个 while 循环，这将使它们成为 O(n)。

但是如果我们使用排序数组，为什么包含是 O(lgn) 和添加/删除 O(n)？

Answer 1

搜索的复杂度为 O(logN)，因为由于数组已排序，您可以应用复杂度为 O(logN) 的二进制搜索。

插入和删除将是 O(N) 复杂度(即线性时间)，因为每次您尝试在排序数组中插入或删除一个元素时，您都必须移动元素您的数组的一个位置是 O(N) 线性时间复杂度。