Как правильно определить сложность времени - лог против линейного - Python - PullRequest
Новая
       23

Как правильно определить сложность времени - лог против линейного - Python

0 голосов
/ 22 января 2019

У меня завтра экзамен на Python по функциональному программированию, анализу времени выполнения и т. Д. *

Я нашел несколько примеров вопросов, которые необходимо проанализировать с точки зрения сложности времени.Я попытался выяснить, почему их сложность во времени такова, но на самом деле не совсем понял.

Коды приведены ниже.Итак, для первого я думал, что эти два первых вызова будут запускать каждый журнал (n).Кроме того, у нас есть операция разрезания каждый раз, которая является линейным временем (n).Так что я догадался, что это большое O из n * log (n) Но мне сказали, что это большое O из n - и я не совсем понял, почему.

Во-вторых, я не могу себе представитьхорошо процедура, так что я думаю, что это большой O журнала (джи).Но правильный ответ - большая буква о джи.И я не понимаю анализа.

Я буду рад получить некоторое объяснение этому анализу во время выполнения.Спасибо. 

def foo(x):
    n = len(x)
    if n <= 1:
        return 17
    return foo(x[:n//2]) + foo(x[n//2:])

def my_sum(i, j): # i <= j
    if i == j:
        return i
    mid = (i + j) // 2
    return my_sum(i, mid) + my_sum(mid + 1, j)
...