我有一个任务听起来像这样：
设 A 是包含 n 个元素的排序列表。我们想添加一些元素 放入 A 中，以便对整个列表也进行排序。
(i( 给出一个 O(n( 算法，该算法将 O(1( 元素添加到 A 中并返回一个排序列表。
(ii( 给出一个 O(n( 算法，该算法将 O(log n( 元素添加到 A 中并返回一个排序列表。
我理解如何使用大 O 符号来描述时间和空间复杂性(在任务中，我假设这两个部分都需要时间复杂度为 O(n((，但在这个任务中，它似乎也描述了元素的数量。真的很难理解。谁能解释一下如何解释"O(1("和"O(log n("部分？
编辑：你有什么建议我应该使用什么类型的算法来完成任务吗？
(i( 你需要将 O(1( 元素添加到 A 中，这意味着你正在添加一个常量元素，即一个元素。因此，您可以通过首先从元素列表(O(n((创建一个链表来添加它。通过迭代任何位置的链表来进一步添加节点将是 O(n(。因此，总体时间复杂度将为 O(n(。
供参考： https://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/
(ii(我们可以首先对要插入的O(log n(元素进行排序，这可以通过合并排序或堆排序等算法在O(log(n(log (log(n((中完成(。 如果 log(n( = k，那么那就是 O(k log(k((。接下来，我们可以合并两个列表(或任何类型的数据结构，只要我们可以按升序迭代它(。这种合并可以在 O(k+n 中完成(，因为我们可以同时迭代两个列表，并且每次"发出"两个列表中最小的一个并前进相应的光标。
因此，总时间复杂度将为 O(n(。
例如，对于两个排序的数组，我们可以将它们合并为：
public static int[] merge_sorted(int[] a, int[] b) {
k = a.length;
n = b.length;
int[] c = new int[k+n];
int ai = 0;
int bi = 0;
int ci = 0;
while(ai < k && bi < n) {
if(a[ai] <= b[bi]) {
c[ci++] = a[ai++];
} else {
c[ci++] = b[bi++];
}
}
while(ai < k) {
c[ci++] = a[ai++];
}
while(bi < n) {
c[ci++] = b[bi++];
}
return c;
}
这些描述要添加到列表中的值集相对于其当前大小 N 的大小。