这些运行次是多少？

Question

我需要比较链表和数组的最坏情况运行时间。

如果必须保留顺序并且 list/array 已经有 n 项，那么以下情况的最坏情况是运行次？为什么？

这些是问题和我的答案：

Adding an item to the front of a linked list. ANSWER ATTEMPT: O(1)
Adding an item to the front of a standard array. ANSWER ATTEMPT: O(n)

Accessing the (n/2):th item of a linked list. ANSWER ATTEMPT: O(n)
Accessing the (n/2):th item of a standard array. ANSWER ATTEMPT: O(1)

Deleting the (n/2):th item from a linked list. ANSWER ATTEMPT: O(1) - CORRECT ANSWER O(n)
Deleting the (n/2):th item from a standard array. ANSWER ATTEMPT: O(n)

Answer 1

Adding an item to the front of a linked list. ANSWER ATTEMPT: O(1)

要在列表的开头添加一个元素，您只需要更改一些指针即可。所以，它的复杂度是O(1).

Adding an item to the front of a standard array. ANSWER ATTEMPT: O(n)

在数组中，要在开头（或中间）添加一个元素，则该索引之后存储的所有元素都需要移动一个位置。所以，在最坏的情况下需要O(n)。

Accessing the (n/2):th item of a linked list. ANSWER ATTEMPT: O(n)

要访问链表中的元素，您需要使用 next 指针从头开始遍历它，因为它们在内存中不连续。因此，需要 O(n) 时间。

Accessing the (n/2):th item of a standard array. ANSWER ATTEMPT: O(1)

数组在内存中是连续的。因此，您可以在 O(1) 时间内使用索引访问第 i 个元素。

除了这个以外的所有答案都是正确的。

Deleting the (n/2):th item from a linked list. ANSWER ATTEMPT: O(1)

删除第(n/2)个元素是O(n)，因为第(n/2)个元素的访问时间不是O(1)。你需要遍历到数组的一半，这是一个O(n)操作。

Deleting the (n/2):th item from a standard array. ANSWER ATTEMPT: O(n)

和添加一样，需要将删除索引后面的元素向前复制过来。因此，需要 O(n) 时间。

这些运行次是多少？

What are the running times of these?

arrays

big-o

linked-list

time-complexity