временная сложность переменных циклов

Question

временная сложность переменных циклов

1

Я хочу попытаться вычислить O (n) моей программы (в python). есть две проблемы:

1: у меня есть очень базовое знание O (n) [aka: я знаю, что O (n) имеет отношение к времени и вычислениям]

и

2: все циклы в моей программе не настроены на какое-либо конкретное значение. они основаны на входных данных.

calccrypto 15 янв. 2010, в 01:56

Источник

2

Это именно то, что N означает в большой записи (то, что вы называете O (n)). N обозначает размер ввода. Это зависит от проблемы. Может быть, вы можете поделиться еще одним контекстом?
R. Martinho Fernandes 15 янв. 2010, в 00:28
3

Ваша вторая «проблема» не является проблемой, о которой вы бы узнали, если бы решили свою первую проблему. Я думаю, что вы должны сначала пройти некоторое базовое изучение, а затем вернуться, если у вас есть более конкретные вопросы.
Mark Byers 15 янв. 2010, в 00:28
0

На самом деле. Если бы не было рекурсии, и все циклы были постоянным числом итераций, сложность по времени была бы O (1).
Anon. 15 янв. 2010, в 00:29
0

Хаха, ты меня взломал! Спасибо тебе за это!
Hamish Grubijan 15 янв. 2010, в 00:36

Показать ещё 2 комментария

Теги:

python

algorithm

big-o

2 ответа

Ещё вопросы

Это именно то, что N означает в большой записи (то, что вы называете O (n)). N обозначает размер ввода. Это зависит от проблемы. Может быть, вы можете поделиться еще одним контекстом?
Ваша вторая «проблема» не является проблемой, о которой вы бы узнали, если бы решили свою первую проблему. Я думаю, что вы должны сначала пройти некоторое базовое изучение, а затем вернуться, если у вас есть более конкретные вопросы.
На самом деле. Если бы не было рекурсии, и все циклы были постоянным числом итераций, сложность по времени была бы O (1).
Хаха, ты меня взломал! Спасибо тебе за это!

pavpanchekha · Answer 1 · 2010-01-14T21-44-00.000Z

n в O(n) означает точно размер ввода. Итак, если у меня есть этот код:

def findmax(l):
    maybemax = 0
    for i in l:
        if i > maybemax:
            maybemax = i
    return maybemax

Тогда я бы сказал, что сложность O(n) - сколько времени она занимает, пропорциональна размеру ввода (поскольку цикл петли столько раз, сколько длина l).

Если у меня был

def allbigger(l, m):
    for el in l:
        for el2 in m:
            if el < el2:
                return False
    return True

то в худшем случае (т.е. когда я возвращаю True), у меня есть один цикл длины len(l) и внутри него один из длины len(m), поэтому я говорю, что он O(l * m) или O(n^2), если ожидается, что списки будут иметь одинаковую длину.

Вам просто нужно знать, как долго вызовы функций в вашем цикле принимают и учитывают их. Например, for i in range(n): if i in arr: do something самом деле O (N ^ 2), а не O (N ), поскольку оператор in занимает O (N) времени.

Travis Bradshaw · Answer 2 · 2010-01-15T01-15-00.000Z

Попробуйте это, чтобы начать, затем перейдите в wiki:

Обычный английский Объяснение примечания Big O