Python-сообщество

Всем добрый день!
Прохожу обучение по Python. Во время обучения есть тесты. Есть вопрос по кортежам:

Какие утверждения про кортежи верные:
1. кортежи могут содержать элементы различных типов
2. проверка на вхождение элемента в кортеж происходит за линейное время
3. проверка на вхождение элемента в кортеж происходит за константное время
4. кортежи изменяемые
5. кортежи неизменяемые

Изначально Я ответил: 1,3,5 и считаю что эти варианты верные. Система говорит обратное. Далее мной были
Из обучающего видео и после поисков в сети Я уверен, что 1 и 5 это верные утверждения. Про время нигде не могу найти информацию.
Прошу подсказать или указать где можно узнать.

Отредактировано a13131 (Сен. 17, 2017 19:39:44)

a13131
Изначально Я ответил: 1,3,5 и считаю что эти варианты верные.

Проверка на вхождение не может осуществляться за константное время. Для проверки вхождения нужно перебрать элементы массива как минимум до нахождения первого вхождения. То есть время линейное.

a13131
Прошу подсказать или указать где можно узнать.

wiki. временная сложность
Линейное время - время, которое можно выразить уравнением прямой (линии).
y = x - прямая
y = 2x - прямая

Для кортежа временная сложность для операции поиска элемента выражается через O(n). Что там в скобках берём - вот это и будет переменная для уравнения.
y = n
Поэтому время линейное.

А как определить временную сложность:
Сколько операций нужно совершить, чтобы найти элемент, который стоит в конце кортежа? Если элементов 10 всего, то нужно каждый элемент взять и посмотреть, чему он равен - то есть две эти операции (взять и посмотреть) десять раз надо сделать. Если элементов 1000 всего, то то же самое - нужно сделать 2000 операций (взять и посмотреть, взять и посмотреть, …). Поэтому при N элементах нужно сделать 2*N операций, чтобы понять, чему равен N-ый элемент.
Получается уравнение y = 2*N, где y - количество операций, а N - количество элементов.
Но так как 1*N, 2*N, 10*N не сильно отличаются, то коэффициент убирают и оставляют N только.

Отредактировано py.user.next (Сен. 17, 2017 13:14:33)

Благодарю всех за ответы!
Особенно за временную сложность алгоритмов.
Тест прошёл.
Действительно, время линейное.