Поиск узла в односвязном списке временной сложности

У меня есть этот вопрос в промежуточном тесте курса DSA:

Предположим, что одиночный связанный список содержит N узлов (N > 8), метод f1() предназначен для поиска 8-го узла от начала, а метод f2() предназначен для поиска 8-го узла от конца. Какова временная сложность f1() и f2()?

Выберите один:

а. Снова и снова)

б. О (1) и О (1)

в. О (1) и О (N)

д. О (N) и О (1)

Дан правильный ответ c. О(1) и О(N). Однако я думаю, что правильный ответ а. Я знаю, что если N = 8, потребуется O (1) времени, чтобы найти 8-й узел с самого начала (просто верните хвостовой узел), но в этом случае N > 8. Может ли кто-нибудь объяснить это для меня, пожалуйста?

Заранее благодарим вас за любую помощь, которую вы можете предоставить.


list algorithm data-structures linked-list singly-linked-list
person L.I.B L.I.B    schedule 18.05.2016    source источник
comment
Ответ правильный, вы - нет. Сколько операций нужно, чтобы вернуть 8-й узел из 1000? Из 1000000?   -  person n. 1.8e9-where's-my-share m.    schedule 18.05.2016
comment
в. является наиболее правильным, но а. также технически правильно, поскольку все, что равно O (1), также является O (N).   -  person Paul Hankin    schedule 19.05.2016

Ответы (1)


arrow_upward
1
arrow_downward

O(1) подразумевает постоянное время работы. Другими словами, это не зависит от размера ввода.

Когда вы применяете это определение здесь, вы можете видеть, что выборка 8-го элемента всегда является постоянной операцией, независимо от размера ввода. Это связано с тем, что независимо от размера ввода (например: 10 100 100..) операция get(8) всегда будет занимать одно и то же время. Кроме того, поскольку мы точно знаем, что n > 8, нет никаких шансов, что попытка получить 8-й элемент приведет к выходу за пределы размера ввода.

person attaboy182    schedule 18.05.2016
comment
O(1) не подразумевает постоянного времени выполнения или того, что время не зависит от размера ввода. Скорее, это означает, что время работы ограничено константой. - person Paul Hankin; 19.05.2016
comment
@PaulHankin, все дело в том, чтобы заставить кого-то понять O (1) . Есть причина, по которой я использовал слово «подразумевать». - person attaboy182; 19.05.2016
comment
Конечно, но есть много недопонимания большого O и сложности, и я не думаю, что хорошие ответы должны включать ошибки. Возможно: O(1) означает, что программа никогда не занимает больше фиксированного количества времени, независимо от входных данных. - person Paul Hankin; 19.05.2016