algorithm - 数据结构 : Big O time cost

Question

1) 向初始为空的单向链表添加 n 个元素的时间成本 插入到列表的前面。

答案似乎是 O(n) 或 O(1) 之一。 我认为它是 O(1) 因为 将一个元素插入空列表只是 例如 Node element = 1;

不过我还是不太确定。

2) 在具有 n 个元素的链表中查找数据元素的最佳情况时间成本是多少。

答案似乎也是 O(1) 或 O(n)。 我认为它是 O(n) 因为它必须遍历列表才能找到元素。

Answer 1

The time cost to add n elements to an initially empty singly linked list by 
inserting at the front of the list.

它是 O(1) 每次插入，但是你有 n 个 - 所以 O(n) 总计。

the best-case time cost to find a data element in a linked list with n elements

它是O(1)，因为在最好的情况下 - 搜索到的元素是第一个，所以不需要遍历列表，搜索完第一个元素(这是常数时间)- 你可以停止。