Вопросы Теги

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

На сервере приложений мы используем то, где я работаю (Oracle Application Server 10g, как я помню), пул обрабатывается сервером приложений. Мы извлекаем javax.sql.DataSource с помощью поиска JNDI с помощью javax.sql.InitialContext .

он сделал что-то вроде этого 

try {     
   context = new InitialContext();
   jdbcURL = (DataSource) context.lookup("jdbc/CachedDS");
   System.out.println("Obtained Cached Data Source ");
}
catch(NamingException e)   
{  
    System.err.println("Error looking up Data Source from Factory: "+e.getMessage());
}

(Мы не пишем этот код, он скопирован из этой документации .)

2
задан user1861872 19 February 2019 в 05:14
поделиться

1 ответ

Если быть более точным, предположим, что у вас есть такая функция: 

T(n) = T(n-1) + T(n-1) + T(n-1), T(0) = 1

Способ, которым это написано. Сложность по времени в точности равна O (3 ^ n).

Ваша функция немного лучше, чем эта функция, но все же сложность по времени та же O (3 ^ n)

Теперь, если мы переписаем мой предложенный код, например: [115 ] 

T(n) = 3 * T(n-1), T(0) = 1

Сложность просто O (n)! потому что результаты предыдущих вызовов повторно используются без повторного вызова.

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

0
ответ дан HmT 19 February 2019 в 05:14
поделиться