Асимптотическая Сложность. Java. Правильно ли я решил тестовое задание?

Question

[Олег Жуков]

Всем привет! Делаю тестовое задание на обучение, кто может помочь с проверкой? Все по теме Асимптотическая Сложность. Язык Java.

Определите асимптотическую сложность следующего алгоритма:

int[] array = new int[n];

for (int i = 0; i <= array.length - 2; i += 2) {

array[i] = i;

}

Ответ O( n/2 )

Используя О-нотацию, укажите через запятую асимптотическую сложность следующих алгоритмов: a) Поиск по ключ в хэш-таблице

b) Доступ по произвольному индексу в массиве

c) Доступ по произвольному индексу в односвязном списке

d) Доступ по произвольному индексу в двусвязном списке

e) Удаление по произвольному индексу в односвязном списке

f) Быстрая сортировка (quick sort) g) Поиск в сбалансированном дереве

Ответ

а) O(1) b) O(1) c) O(N) d) O(N) e) O(1) f) O(n log(n)) g) O(log n)

Answer 1

[Денис Загаевский]

Вы не до конца понимаете, что такое ассимптотическая сложность. "Ответ O( n/2 )" - в корне неверный, потому что О подразумевает любой константный множитель. Если бы даже был цикл от 1 до n*100..миллард..нулей..00, сложность всё равно была бы О(n).
е) неверно. Для того, чтобы удалить произвольный элемент связного списка, надо сначала его найти.
f) неверно, q-sort без модификаций может вырождаться в O(n^2). O(n log n) в среднем.
Остальное верно.

Comments

[Олег Жуков]

спасибо! вот еще ссылка на этот же вопрос на stackoverflow ru.stackoverflow.com/questions/596896/%D0%90%D1%81... кому может пригодиться