DjangoBB LoFi version

Полная версия: Ассимптотная часовая сложность

Начало » Центр помощи » Ассимптотная часовая сложность

OleksandrSanin

Ноя. 12, 2016 01:46:04

 def function(n):
    for i in range(n):
        if i == 0:
            for j in range(n):
                for k in range(10000):
                    print("Karlik")

Какая ассимптотная часовая сложность функции function по отношению к n?
Сколько раз выпишется слово “Карлик” по отношению к n?
Spasibo!

JOHN_16

Ноя. 12, 2016 10:29:31

OleksandrSanin
код на форумах нужно оформлять в теги code

izekia

Ноя. 12, 2016 11:41:53

n*10000/n
слова выше не знаю

scidam

Ноя. 12, 2016 12:11:18

Видимо, код должен быть таким:

 def function(n):
   for i in range(n):
       if i == 0:
           for j in range(n):
               for k in range(10000):
                    print(“Karlik”)

Если он такой, то:
1) При i = 1, .. n будет выполнена проверка i==0 c результатом False, это потребует n-1 “операций”
2) При i =0 Будет выполнено n*10000 “операций” напечатать Karlik
Т.о. всего “операций” n*10000 + n - 1
Асимптотическая сложность: O(n*10000 +n -1) = O(n) (из определения О-большого), т.е. O(n)
Сколько карликов: 10000n