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) 吗？

Answer 1

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

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

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

任何其他转换也与格式或结果字符串的通常恒定大小成线性关系，因此通过许多假设，您可以说它是 O(1)。

此外，您的代码表明输出仅发生在实际测试功能时，根本不应被视为计算的一部分。最好的方法是将 I/O 从您想要考虑的函数中移出，以提高复杂性，例如移至函数中，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;
}