algorithm - 链表的时间复杂度是多少

Question

使用 for 循环的链表的运行时复杂度是多少？根据我的理解，它是 0(n)。我不确定我的回答是否正确。

import java.util.LinkedList;
import java.util.List;

public class Test1 {

	public static void main(String[] argv) {
		List<Integer> r;

		// Displays entire sequence for 1 child
		System.out.println("Sequence for 1 child");
		System.out.println(r = func1(1, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

		// Displays entire sequence for 2 children
		System.out.println("Sequence for 2 children");
		System.out.println(r = func1(2, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

		// Displays entire sequence for 3 children
		System.out.println("Sequence for 3 children");
		System.out.println(r = func1(3, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

		// Displays entire sequence for 4 children
		System.out.println("Sequence for 4 children");
		System.out.println(r = func1(4, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

		// Displays entire sequence for 5 children
		System.out.println("Sequence for 5 children");
		System.out.println(r = func1(5, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

		// Displays entire sequence for 6 children
		System.out.println("Sequence for 6 children");
		System.out.println(r = func1(6, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

		// Displays entire sequence for 7 children
		System.out.println("Sequence for 7 children");
		System.out.println(r = func1(7, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

		// Displays entire sequence for 8 children
		System.out.println("Sequence for 8 children");
		System.out.println(r = func1(8, 2, 1));
		// Displays the last person
		System.out.printf("The Winner is %d \n", r.get(r.size() - 1));
		System.out.println("----------------------------------------");

	}

	// Remove N elements in equal steps starting at specific point
	public static List<Integer> func1(int N, int step, int start) {
		if (N < 1 || step < 1 || start < 1) {
			return null;
		}

		List<Integer> p = new LinkedList<Integer>();
		for (int i = 0; i < N; i++) {
			p.add(i + 1);

		}

		List<Integer> r = new LinkedList<Integer>();
		int i = (start - 2) % N;
		for (int j = N; j > 0; j--) {
			i = (i + step) % N--;
			r.add(p.remove(i--));
			// System.out.println(r);
		}

		return r;
	}

}

输出如下1个 child 的顺序[1]

获胜者是 1

2 个 child 的顺序[2, 1]

获胜者是 1

3 个 child 的顺序[2, 1, 3]

获胜者是 3

4 个 child 的顺序[2, 4, 3, 1]

获胜者是 1

5 个 child 的顺序[2, 4, 1, 5, 3]

获胜者是 3

6 个 child 的顺序[2, 4, 6, 3, 1, 5]

获胜者是 5

7 个 child 的顺序[2, 4, 6, 1, 5, 3, 7]

获胜者是 7

8 个 child 的顺序[2, 4, 6, 8, 3, 7, 5, 1]

获胜者是 1

Answer 1

长话短说:

您的第一个循环是 O(N)，第二个是 O(N^2)。

(不是这样)详细解释:

您的第一个循环是 O(N)，因为您正在访问列表中的所有元素，并且每个 add 调用都是 O(1)。

来自Java的官方文档:

public boolean add(E e) Appends the specified element to the end of this list. This method is equivalent to addLast(E).

如果你必须使用 add(int index, E e)，这将是 O(N^2) 因为这个带有 2 个参数的函数有一个时间O(N) 访问的复杂性，访问 N 次 O(N) 函数给你 O(N^2) 。然而，这不是你的情况。

另一方面，您的第二个循环是 O(N^2)，因为您要添加一个具有 O(1) 的元素，但您还删除了一个使用 delete(int index) 的元素需要 O(N)。此方法采用 O(N)，因为首先，它会在您要访问的位置搜索节点，然后删除更改指针引用的元素。请记住，LinkedList 没有直接访问权限，它具有指针，O(1) 仅适用于同时涉及头元素和尾元素或使用迭代器的操作。