因此,我的 comp sci 类(class)中的主题之一是关于时间复杂度以及使用数组和链表作为比较某些操作的好方法以及哪种容器更擅长这样做,因此您可以选择合适的数据结构。 我理解大多数操作背后的原因,但我不确定其中一个操作是在数组中插入和追加。
这两种情况的最坏情况是 O(n)。我相信我理解为什么插入是 O(n),因为最坏的情况是,您在前面插入导致您将所有元素移到右边,这意味着它是线性的并且取决于数组中元素的数量。 对于追加,我很好奇为什么它不是 O(1),因为考虑到有空间,无论大小如何都需要一次操作才能在末尾添加一个元素。
这是问题吗,如果没有足够的空间,您必须将数组复制到更大的数组以应对最坏的情况?
最佳答案
[...] if there isn't enough space you have to copy the array to a larger one for its worst case scenario?
宾果。
关于c++ - 数组操作的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19235290/