printf()函数的时间复杂度是多少？

Question

我希望确定类似以下 printf 的时间复杂度：

{
    printf("%d",
           i);
}

或者：

{
    printf("%c",
           array[i]);
}

假设printf函数的时间复杂度始终为O(1)，这种假设是否正确？

[编辑] 我们来看一个交换两个值的函数：

void swap(...)

{

      tmp = x;
      x = y;    
      y = tmp;  

}

每个赋值表达式的时间复杂度为1，因此T(n) = 1 + 1 + 1 = 3，即O(1)。但是对于这个函数，我能说什么呢？

void swap(...)

{

      tmp = x;
      x = y;    
      y = tmp;  

      printf("Value of x: %d", x);
      printf("Value of y: %d", y);

}

在这种情况下，我可以说T(n)仍然是O(1)吗？

- LordFenerSSJ

---

这是O(n)的时间复杂度，其中n是输出长度。可能是这样，前提是有很多假设，有些合理，有些不太合理。 - Deduplicator

这是O(1)，因为固定宽度整数的集合是有限的... - 5gon12eder

snprintf（...）返回将被打印的字符数，即使实际打印的字符较少。因此，snprintf（buffer，1，“％s”，some string）的时间是无限的，最多只打印1个字节。 - gnasher729

Answer 1

我认为这不是一个明智的问题，因为printf的行为大多是实现定义的。C语言没有对系统在遇到printf时应该做什么进行任何限制。它确实有一个“流”的概念。C11标准的第7.21节规定，printf作用于一个流上。

C语言允许实现在写入流后对其进行任何操作(7.21.2.2)：

“字符可能需要添加、更改或删除，以符合主机环境中表示文本的不同约定。因此，流中的字符和外部表示中的字符之间可能不存在一对一的对应关系。”

因此，当打印char时，你调用printf可以输出1TB，而打印int时则可以输出1字节。

标准甚至不要求在调用printf时立即发生写操作(7.21.3.3)：

当流是未缓冲的时，字符应该尽快从源或目的地中出现。否则，字符可能会被积累并作为块传输到或从主机环境中。当流完全缓冲时，当缓冲区被填满时，字符应该作为块被传输到或从主机环境中...对这些特性的支持是实现定义的。而标准并没有指定stdout是缓冲还是未缓冲。所以，C允许printf在你请求写入的时候做任何它觉得合适的事情。

- Patrick Collins

---

实际上，对于任何合理的系统调用含义而言，printf 都不是一个系统调用。printf 是由 C 标准（例如 ISO 9899:1999）定义的 库函数，通常在 libc 中实现。 - fuz

@FUZxxl 我的理解是，IO始终是您要求操作系统在最低级别上执行的操作。我已经进行了编辑，试图解决您的评论，如果仍然不准确，请告诉我。 - Patrick Collins

现在好多了。 printf通常（即始终）被实现为一个函数，该函数解释格式化字符串，创建输出，然后使用fwrite()和fputc()等函数将输出发送到stdout。 FILE API的实现反过来使用系统调用（在类unixoid系统上使用write()）将数据发送到操作系统。printf本身不应直接调用操作系统。 - fuz

此外，系统调用的通用定义是指“对操作系统的函数调用，其唯一目的是在不预处理参数的情况下向操作系统发出调用”。 - fuz

Answer 2

评估 printf() 的时间复杂度有些奇怪，因为它是一种阻塞的输入/输出操作，通过中间缓冲层执行一系列的 write() 系统调用来执行一些文本处理和写操作。

文本处理部分的最佳猜测是必须读取整个输入字符串并处理所有参数，所以除非有黑魔法，否则可以将复杂度视为 O(n) 到字符数。通常不需要动态提供 printf() 的格式参数，因此大小已知，因此有限，因此复杂度确实是 O(1)。

另一方面，阻塞输出操作的时间复杂度没有上限。在阻塞模式下，所有的 write() 操作要么返回错误，要么至少写入一个字节。假设系统准备好在恒定的时间内接受新数据，那么您也会得到 O(1)。

任何其他转换也与格式或结果字符串的典型常量大小成正比，因此在一些假设下，可以认为它是 O(1)。

此外，您的代码表明输出仅用于测试功能，并且不应该被视为计算的一部分。最好的方法是将输入/输出从您想考虑为目的复杂度的函数中移出，例如将其移到 main() 函数中以强调输入和输出仅用于测试代码。

没有 I/O 的 O(1) 交换函数的实现：

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

没有使用临时变量的替代实现（只是为了好玩）：

void swap(int *a, int *b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

主要功能的实现：

int main(int argc, char **argv)
{
    int a = 3, b = 5;

    printf("a = %d; b = %d\n", a, b);
    swap(&a, &b);
    printf("a = %d; b = %d\n", a, b);

    return 0;
}

- Pavel Šimerda

Answer 3

一般来说，printf()的时间复杂度为O(N)，其中N是输出的字符数。并且这个数量不一定是一个小常数，例如以下两个调用：

printf("%s", myString);
printf("%*d", width, num);

myString的长度并没有一个上限，因此第一次调用的复杂度是O(strlen(myString))，而第二次调用将输出width个字符，预计需要花费O(width)的时间。

然而，在大多数情况下，printf()输出的量会受到一个小常数的限制：格式字符串通常是编译时常量，像上面计算的字段宽度很少使用。字符串参数更频繁，但通常也允许给出一个上限（比如当您从错误消息列表中输出字符串时）。因此，我敢打赌，至少90%的真实世界中的printf()调用是O(1)的。

- cmaster - reinstate monica

Answer 4

时间复杂度并不是指运行特定程序所需的时间。时间复杂度是以运行所需的频率数量来衡量的。现在，如果你考虑简单的printf()语句，显然时间复杂度将为O(1)。

参考： 算法的时间复杂度

- Avinash

---

“它需要运行的频率数量”没有任何意义。 "它需要运行的频率数量" 也是一样。 频率是每秒发生多少次的度量。说“它需要每秒运行的次数”毫无意义。 - Patrick Collins

前提是错误的，正如我在我的答案中所述：C标准不要求printf具有任何特定的时间复杂度。 - Patrick Collins

@Avinash，您发布的链接是错误的。它的英语和计算机科学都是错误的。它基本上是胡言乱语。 - Patrick Collins

随着模块n的增加，与算法执行时间的增长率和f(n)的增长率成比例，因此f(n)越小，算法的时间复杂度就越低，算法效率就越高。 - Patrick Collins

@Avinash，你是在暗示说，如果我写一个10层嵌套的for循环，导致时间复杂度为O(n^10)，只要我将其封装在一个函数调用中，那么因为我只调用一次该函数，它就突然变成了O(1)？ - OJFord