определение эффективности программы и как ее рассчитать на примерах.

  1. компьютеры работают быстро и становятся быстрее — так что, может быть, эффективные программы не имеют значения?
  2. но наборы данных могут быть очень большими
  3. таким образом, простые решения могут просто не масштабироваться приемлемым образом.
  4. так как же мы можем решить, какой вариант программы наиболее эффективен?
  5. раздельная эффективность программы по времени и пространству  компромисс между ними — основное внимание будет уделяться эффективности времени

ПОРЯДКИ РОСТА

Цели:

  • хотите оценить эффективность программы, когда ввод очень большой
  • хотите выразить рост времени выполнения программы по мере увеличения размера входных данных
  • хочу установить верхнюю границу роста
  • не нужно быть точным: «порядок» не «точный» рост
  • мы рассмотрим самые большие факторы времени выполнения (какой раздел программы будет выполняться дольше всего?)

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

Программа 1:

def program1(x):
    total = 0
    for i in range(2000):
        total += i

    while x > 0:
        x -= 1
        total += x

    return total

Какое количество шагов потребуется для запуска программы 1 в лучшем случае? Выразите ответ через n, размер входных данных x.
В лучшем случае x меньше или равен 0. Сначала мы выполняем присваивание total = 0 за один шаг. Затем мы выполняем цикл for i in range(2000). Этот цикл выполняется 2000 раз и имеет три шага (один для присвоения i каждый раз в цикле, а также два для операции +=) на каждой итерации. Далее мы проверяем, если x › 0 — это не так, поэтому мы не входим в цикл. Добавляя еще один шаг для оператора return, в лучшем случае мы выполняем 1 + 3*2000 + 1 + 1 = 6003 шага.

Какое количество шагов потребуется для запуска программы 1 в худшем случае? Выразите ответ в терминах n, размер входных данных x.
В худшем случае x — большое положительное число. В этом случае мы сначала выполняем присваивание total = 0 за один шаг. Далее мы выполняем первый цикл 2000 раз (всего 6000 шагов), затем выполняем второй цикл (пока x > 0) n раз. Этот цикл состоит из пяти шагов (один для условной проверки, x > 0 и по два для операций -= и +=). Когда мы, наконец, доходим до точки, где x = 0, мы в последний раз выполняем условную проверку x › 0 — поскольку это не так, мы не входим в цикл. Добавляя еще один шаг для оператора return, в худшем случае мы выполняем 1 + 32000 + 5n + 1 + 1 = 5*n + 6003 шагов.

Программа 2:

def program2(x):
    total = 0
    for i in range(1000):
        total = i

    while x > 0:
        x = x//2
        total += x

    return total

Какое количество шагов потребуется для запуска программы 2 в худшем случае? Выразите ответ в терминах n, размер входных данных x.

В худшем случае x — большое положительное число. В этом случае мы сначала выполняем присваивание total = 0 для одного шага, затем выполняем первый цикл 1000 раз (всего 2000 шагов). Наконец, выполните второй цикл (пока x > 0) log2(n) + 1 раз. Это сложно! Поскольку мы делим x на 2 каждый раз в цикле, мы выполняем этот цикл только логарифмическое число раз. log2(n) деления x на 2 даст нам x = 1; нам понадобится еще одно деление, чтобы получить x ‹= 0 .

Этот цикл while состоит из пяти шагов (один для условной проверки, x > 0 и по два для операций //= и +=). Когда мы, наконец, доходим до точки, где x = 0, мы выполняем условную проверку x › 0 в последний раз — поскольку это не так, мы не входим в цикл. Добавляя один шаг для оператора return, в худшем случае мы выполняем 1 + 21000 + 5(log2(n) + 1) + 1 + 1 = 5*log2(n) + 2008 шагов .

Программа 3:

def program3(L):
    totalSum = 0
    highestFound = None
    for x in L:
        totalSum += x

    for x in L:
        if highestFound == None:
            highestFound = x
        elif x > highestFound:
            highestFound = x

    return (totalSum, highestFound)

Какое количество шагов потребуется для запуска программы 3 в худшем случае? Выразите ответ через n, количество элементов в списке L.

В худшем случае L — это список, элементы которого отсортированы в возрастающем порядке (например, [1, 3, 5, 7, …]). В этом случае мы выполняем первые два оператора присваивания (2 шага). Далее мы выполняем первый цикл n раз. Этот первый цикл состоит из трех шагов (один для присвоения x каждый раз в цикле, а также два для операции +=), добавляя 3*n шагов.

Наконец, мы выполняем второй цикл n раз. При первом выполнении этого цикла мы выполняем 3 шага — один для присвоения x; затем запускаем проверку ifhighthFound==None и, обнаружив, что это True, выполняем присваиваниеhighestFound=x.

Следующие (n-1) раз мы выполняем этот цикл, мы выполняем 4 шага: один для присвоения значения x, затем мы запускаем проверку, если highFound == None, и, обнаружив, что оно равно False, мы запускаем проверку elif x ›highestFound. Так как это всегда True (список отсортирован в порядке возрастания), мы выполняем присваивание highFound = x. Поэтому во втором цикле выполняем 3 + (n-1)4 = 3 + 4n — 4 = 4*n — 1 шагов.

Наконец, мы выполняем оператор return, что является еще одним шагом.

Собрав все это вместе, мы видим, что в худшем случае мы выполняем 2 + 3n + 4n — 1 + 1= 7*n + 2 шага.