c++ - 排序数组的计算复杂度

Question

目前，我正在为我的大学做一个项目，我在其中实现已知的数据结构(数组、链表、BST 等)，我必须测量对它们进行某些操作所需的时间。例如，对我来说第一个是数组。我已经测量了在数组中间添加一个元素的时间(移动了更多的 c 值，所以 n = n + 1。它当然给了我 O(n)，其中 n 是元素的数量。现在我必须检查是否将一个元素添加到数组的开头并将一个元素附加到它(添加到末尾)。我有 2 个简单的算法(我不能使用STL 或 boost::):

添加到开头:

void array::beginning_append(int value)
{   
    int *temp = new int[n + 1];
    memcpy(temp + 1, table, sizeof(int) * n);
    n = n + 1;
    temp[0] = value;
    delete[] table;
    table = new int[n];
    memcpy(table, temp, sizeof(int) * n);
    delete[] temp;
}

追加到最后:

void array::append(int value)
{
    int *temp = new int[n + 1];
    memcpy(temp, table, sizeof(int) * n);
    temp[n] = value;
    n = n + 1;
    delete[] table;
    table = new int[n];
    memcpy(table, temp, sizeof(int) * n);
    delete[] temp;
}

那些是方法或array 类，其中table 和n 是此类的成员。现在那些差别不大，我认为它们的时间是相同的，它们是(我用 QueryPerformanceCounter 检查了大量元素，比如 500000，它给了我 O(n) 的复杂性)，但我的讲师说添加到开头将具有 O(n) 的计算复杂性，但从末尾添加或删除元素将具有 O(1) 的复杂性，因此无论元素的数量如何，它都是 const。所以我想问问你们我的算法是否不好，我的意思是它们做了不必要的事情，这就是为什么它们依赖于元素的数量，或者我的讲师错了

Answer 1

两种复杂度是:

O(n)

因为您正在复制整个数组。

查看更多关于memcpy() here 的复杂性。

---

提示:您可以轻松跳过第二个拷贝，方法是释放table 指向的内存，然后使其指向temp。这样你只会复制一次，而不是两次。但是整体的时间复杂度不会改变。

例子:

void array::prepend(int value)
{   
    int *temp = new int[n + 1];
    memcpy(temp + 1, table, sizeof(int) * n);
    n = n + 1;
    temp[0] = value;
    delete[] table;
    table = temp;
}

---

专业提示:How do you detect/avoid Memory leaks in your (Unmanaged) code?

_{预感:realloc() 的巧妙实现应该比对新数组的粗暴的 memcpy() 执行得更快。原因是，如果 realloc() 能够扩大/缩小您的数组，而不必将整个内容复制到一个新位置(当没有足够的连续空间时可能会发生)，那么它会更快。 realloc() 并不总是意味着 O(1)。}