的printf

2013-05-29 32 views 6 likes

假設我打印字符串的漸近複雜性，具體如下：的printf

printf("%s", s);

我們可以假設這個函數的漸近複雜性？

是否O（n）其中n是strlen（s） - 它的長度是多少？或者它不知何故是不變的。或者有些不同？不過，我想你應該知道printf是如何實現的。任何見解都被讚賞！

（我要澄清，我說的是C而不是C++，但我懷疑他們的實現方式不同）

編輯：添加格式化字符串的printf（）

2013-05-29 Miguel

正確的語法是'printf（「％s」，stringName）;'。 –

有沒有很好的理由呢？畢竟，s已經是一個字符串了，那麼爲什麼它需要被printf格式化呢？ – Miguel

@Miguel是的，因爲它可能包含自己的格式代碼，並且會產生未定義的/未知的/不可預知的/可能的_very_bad結果。 –

回答

它的複雜度爲O （m + n），其中m是輸入的大小，n是輸出的大小。

如果不傳遞額外的參數，如在你的情況下時間複雜度是O（2 * m）= O（m）。

但請注意，您的代碼可能會失敗，因爲s本身可能包含格式代碼，並且會產生Adriano指出的未定義/未知/不可預測/可能_very_bad結果。

2013-05-29 15:18:38

所以你說它在每個字符上迭代一次格式化，然後一次輸出？難道它只是內存轉儲到輸出流，或者是O（m）嗎？ – Miguel

我總是認爲'printf'只是輸出結果，當它遇到'％d'或'％s'時，它會採取適當的參數並將其打印出來，因此，它的複雜性將是線性的論據。 –

@SukritKalra但打印出一個字符串不是O（1）。 – effeffe

相關問題