f（n）= N的大O！ + 2^N

我檢查功能f（n）= N的大O！ + 2^N

f(n) = N! + 2^N

據稱，這是

O(N^N)

我不太清楚這是爲什麼，以及如何證明這是真的。

我會認爲它是

O(N!)

你能提供一個解釋，爲什麼大O的

f(n) = N! + 2^N => O(N^N)

來源

2014-02-09 ceptno

這個問題似乎是脫離主題，因爲它不是關於編程。它真的屬於[cs.se] – 2014-02-09 21:11:52

因爲N！是大的，真的很大http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions，如需瞭解更多信息，請參閱上面提到的CS角落 – user2485710

我的錯誤@MikeW。將來，我會把我的大O問題放在那裏。 – ceptno

這的確是O(N!)，自N!是O(N^N)（因爲N! < = N^N所有N> 0），O(N!)中的任何內容也都在O(N^N)中。

來源

2014-02-09 21:15:29 sepp2k

它是'=>'不是'<=' – user2485710

這是否被認爲是一個相對緊張的界限？ N之間有特殊關系嗎？和N^N我應該考慮我所有的大O問題？ – ceptno

@ user2485710不，它是<=。 N^N是'N * N * ... * N'。 'N！'是'1 * 2 * ... * N'。在這兩種情況下，您都有相同數量的術語，並且'N！'中的術語都小於或等於N，而'N^N'中的術語全部都是'N'。所以'N！ <= N^N'。另請注意，如果N！大於「N^N」（非常數因子），「N！」不會是「O（N^N）」，所以問題的前提是錯誤的。 – sepp2k

f（n）= N的大O！ + 2^N

回答

相關問題