Как анализировать время работы Python For-L oop?

Question

Рассмотрим следующий построчный анализ классического for-l oop:

1 for (int i = 0; i < N; i++) {    | 1 + N + (N - 1)
2                                  |
3     //do something               | c
4                                  |
5 }                                |

В этом примере для инициализации for-l oop требуется одна примитивная операция, условие l oop проверяется N раз, а переменная i увеличивается N - 1 раз, в то время как тело l oop принимает c операций примита для некоторой константы c. Это означает, что строка 1 выполняется 1 + N + (N - 1) раз, а тело l oop выполняется N раз. Однако в Python этот анализ не будет работать, потому что циклы for в Python реализуются с использованием итераторов. Рассмотрим следующий простой пример:

1 for i in range(len(N)):          | ?
2     //do something               | c

Если бы я хотел построчно проанализировать время работы этого фрагмента кода, как я уже делал выше, как бы я это сделал? Должен ли я предполагать, что строка 1 выполняется N раз, как в классическом for-l oop, или имеет смысл сказать, что в Python строка 1 выполняется один раз, и только тело l oop выполняется N раз?

Answer 1

Похоже, вы пытаетесь вычислить асимптотику, но не понимаете, как это работает: (

Вы не можете сказать, что классический for-l oop (например, c ++) выполняет T(C * (1 + N + (N - 1)), потому что все зависит от 1000 и еще 1 вещи, например, компилятор ...

Если вы хотите вычислить асимптотику (в наши дни) - лучше используйте O-нотацию, которая говорит, что оба кода выполняются с O(C * N) операциями.

Answer 2

range() дает вам итератор. Получение следующего значения из итератора - это операция O(1). For l oop просто выбирает следующее значение из итератора N раз, что делает его N * O(1) или O(N). L oop завершается, когда итератор вызывает StopIteration, который обрабатывается for-l oop для выхода из l oop. Это тоже O(1).

Высокоуровневые операции в python нельзя точно подсчитать, как в C.