泛型算法时间复杂度分析：是否需考虑泛型类型的大小？

在确定泛型算法的时间复杂度时，是否需要将泛型类型的大小纳入考量？比如下面这个C++泛型函数，它按字节将一个对象从内存的一个位置复制到另一个位置：

template<typename Type>
void copy(Type & destination, const Type & source)
{
    char * destination_pointer { reinterpret_cast<char *>(&destination) };
    const char * source_pointer { reinterpret_cast<const char *>(&source) };

    for(std::size_t index { 0 }; index < sizeof(Type); ++index)
        destination_pointer[index] = source_pointer[index];
}

针对这个函数的时间复杂度，有两种常见解读：

• 解读一：线性时间O(n)，n为Type的大小
  从泛型算法的通用性角度看，不同的Type对应不同的sizeof(Type)，循环执行的次数会随类型大小线性增长，函数实际耗时也会随之线性增加。比如复制1字节的char和1024字节的自定义结构体，循环次数相差1024倍，实际运行时间差距明显，这种情况下用O(n)描述是合理的。

• 解读二：常数时间O(1)，针对特定类型
  当Type固定时，sizeof(Type)是一个确定的常数，不管该类型的实例值是什么，函数的循环次数固定，执行时间也保持稳定。比如针对int类型调用这个函数，所有int实例的复制耗时都一致，符合常数时间的特征。

结论 #

两种解读都不算错误，核心差异在于分析的上下文和关注的维度：

• 如果关注泛型算法适配不同类型时的性能变化，那么O(n)（n为类型大小）的描述更准确；
• 如果聚焦于某一具体类型的调用场景，或者讨论算法在固定类型下的表现，O(1)的描述是恰当的。

在常规算法分析语境中，讨论泛型算法时通常会明确参数维度。比如STL的std::copy复制单个对象时，对固定类型T是O(1)；复制N个T对象时则是O(N)，这里的变量是元素数量N，单个T的大小被视为常数。

内容的提问来源于stack exchange，提问作者Pharap