Mig*_*ell 6 c c++ big-o printf asymptotic-complexity
假设我正在打印一个字符串,如下所示:
printf("%s", s);
我们可以假设这个函数的渐近复杂性是什么？
它是O(n),其中n是strlen(s) - 它的长度是多少？或者它是某种方式O(1),恒定的时间.或者不同的东西？不过,我认为你需要知道printf是如何实现的.任何见解都表示赞赏!
(我应该澄清一点,我说的是C而不是C++,但我怀疑它们的实现方式不同)
编辑:将格式字符串添加到printf()
它的复杂性是O(m + n),其中m是输入的大小,n是输出的大小.
如果没有传递其他参数,例如在你的情况下时间复杂度是O(2*m)= O(m).
但请注意,您的代码可能会失败,因为s可能包含格式代码本身,并且会产生未定义/未知/不可预测/ might_very_bad结果,如Adriano所指出的那样.