printf函数的渐近复杂度

Question

假设我要打印一个字符串，如下所示：

printf("%s", s);

我们可以假设这个函数的渐进复杂度是什么？

它是 O(n)，其中 n 是 strlen(s) - 字符串的长度吗？还是以某种方式为常量时间的 O(1)。或者是其他东西？我想你需要知道 printf 通常是如何实现的。任何见解都将不胜感激！

（我应该澄清一下，我说的是 C 而不是 C++，但我怀疑它们实现上有所不同）

编辑：在 printf() 中添加格式化字符串

- Migwell

---

正确的语法是 printf("%s", stringName);。 - Sukrit Kalra

有什么好的理由吗？毕竟，s已经是一个字符串了，为什么还需要通过printf进行格式化呢？ - Migwell

@Miguel是的，因为它 可能 包含格式代码本身，这将产生未定义/未知/不可预测/可能非常糟糕的结果。 - Adriano Repetti

s="%d"; printf(s); 会导致程序崩溃。复杂度显然是O(n)。 - Dmitry Galchinsky

我曾经认为，像在memcpy()中一样复制已知大小的内存块会更快，但正如这个线程告诉我的：https://dev59.com/5XRC5IYBdhLWcg3wP-j4，情况并非如此（虽然速度更快，但并不是数量级上的提升）。 - Migwell

Answer 1

它的复杂度为O(m + n)，其中m是输入的大小，n是输出的大小。

如果不像你的情况那样传递额外的参数，时间复杂度为O(2*m) = O(m)。

但要注意，你的代码可能会失败，因为s本身可能包含格式化代码，这将产生未定义/未知/不可预测/可能非常糟糕的结果，正如Adriano所指出的那样。

- sasha.sochka

---

那么你的意思是它在格式化时只迭代一次每个字符，然后在输出时再迭代一次？它不能直接将内存转储到输出流中吗，或者无论如何都是O(m)吗？ - Migwell

我一直认为 printf 只是将结果原样输出，当遇到 %d 或 %s 时，它会取相应的参数并打印出来，因此，它的复杂度将是其第一个参数的线性。 - Sukrit Kalra

@SukritKalra 但是打印字符串不是O(1)。 - effeffe

我的意思是第一个参数的长度是线性的。因此，时间复杂度为O(n)。 - Sukrit Kalra

@SukritKalra 我不确定我理解你的意思：整个函数的复杂度不仅取决于格式字符串，而且还取决于必须打印的其他参数的长度，这是任意的并且与格式字符串相当独立的；而且可能有很多参数。 - effeffe

@effeffe，你说得对，这就是为什么当参数存在时复杂度为O(m+n)。 - sasha.sochka