определение эффективности программы и как ее рассчитать на примерах.
- компьютеры работают быстро и становятся быстрее — так что, может быть, эффективные программы не имеют значения?
- но наборы данных могут быть очень большими
- таким образом, простые решения могут просто не масштабироваться приемлемым образом.
- так как же мы можем решить, какой вариант программы наиболее эффективен?
- раздельная эффективность программы по времени и пространству компромисс между ними — основное внимание будет уделяться эффективности времени
ПОРЯДКИ РОСТА
Цели:
- хотите оценить эффективность программы, когда ввод очень большой
- хотите выразить рост времени выполнения программы по мере увеличения размера входных данных
- хочу установить верхнюю границу роста
- не нужно быть точным: «порядок» не «точный» рост
- мы рассмотрим самые большие факторы времени выполнения (какой раздел программы будет выполняться дольше всего?)
Примеры: рассчитать шаги, необходимые для запуска каждой программы.
Программа 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 шага.