Блог

Главная - Вопросы по программированию - Временная сложность использования нескольких функций?

Временная сложность использования нескольких функций?

#python #function #time-complexity

#python #функция #временная сложность

Вопрос:

Допустим, мы используем 2 функции за один раз:

sorted(list(str_variable)) — Python использует Timsort, сложность которого равна NlogN — так что общая сложность этого становится: N^2*logN

Это будет рассматриваться как функция внутри функции, и поэтому сложности будут умножаться ( O(N) для list() и O(NlogN) для sort() .

Но я мог бы также написать:

 s = list(str_variable)
res = sorted(s)

В каком случае его просто O(N) использовать O(N NlogN) ?

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

Комментарии:

1. это не так, как это работает. сначала list(str_variable) выполняется, а затем sorted( answer ) выполняется, по сути, обе вышеуказанные функции должны занимать одинаковое количество времени.

2. вы можете попробовать: import time; start_time = time.time(); <your code>; print( time.time() - start_time) чтобы увидеть разницу, я бы поспорил, что первый быстрее. 🙂

3. Я понимаю, что они оба займут примерно одно и то же время, потому что логически я понимаю, что они оба будут казнены. Можете ли вы объяснить, используя сложности the big o? Это та часть, которую я пытаюсь понять.

4. Внутренне они выполняются так, как вы показали при втором выполнении. Итак, ваша 2-я нотация Big O верна.

5. Ваше первое предположение неверно … между ними нет никакой разницы…

Ответ №1:

Если у вас есть вложенные вызовы функций, их сложность не увеличивается.

Допустим, ваш вызов

 f(g(N))

А временные сложности f и g на входах размера N равны F(N) и G(N) , соответственно. Тогда общая временная сложность равна

 G(N)   F(size(g(N))

В вашем примере f есть sorted и g есть list , поэтому мы имеем следующее:

 F(N) ∈ O(N log N)
G(N) ∈ O(N)
size(g(str_variable)) = N

Таким образом, общая сложность

   G(N)   F(size(g(N))
∈ O(N)   O(N log N)
= O(N log N)    since O(N) ⊂ O(N log N)

Ответ №2:

Это не так, как это работает, сначала list(str_variable) выполняется, а затем sorted(answer) выполняется, по сути, обе вышеперечисленные функции должны занимать одинаковое количество времени.

Внутренне он выполняется так, как вы показали во 2-м фрагменте кода, поэтому вы можете просто использовать те же обозначения.

Вы можете попробовать и проверить это так же:

 import time
now = time.time()
sorted(list(str_variable))
print(time.time() - now )


now = time.time()
s = list(str_variable)
res = sorted(s)
print(time.time() -now)

Я готов поспорить, что первый работает быстрее😉

Метки: