Какова будет сложность времени для связанных списков

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 ребенка [1]

Победитель - 1

Последовательность для 2 детей [2,1]

Победителем является 1

Последовательность для 3 детей [2, 1, 3]

Победителем является 3

Последовательность для 4 детей [2, 4, 3, 1]

Победитель 1

Последовательность для 5 детей [2, 4, 1, 5, 3]

Победитель 3

последовательность для 6 детей [2, 4, 6, 3, 1, 5]

победитель 5

последовательность для 7 детей [2, 4, 6, 1, 5, 3, 7]

Победитель 7

Последовательность для 8 детей [2, 4, 6, 8, 3, 7, 5, 1] ​​

Победитель 1

Answer 1

TL; DR:

Ваш первый цикл O(N), а второй O(N^2).

(не так) Длинное объяснение:

Ваш первыйцикл равен O(N), потому что вы обращаетесь ко всем элементам в списке, и каждый вызов add равен O(1).

Из официальной документации Java:

public boolean add(E e) Добавляет указанный элемент в конец этого списка.Этот метод эквивалентен 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) предназначен только для операций, которые включают элементы head и tail или используют итератор.