algorithm - 以下大 O 表示法函数的时间复杂度是多少？

Question

我正在努力理解大 O，但遇到了一个棘手的问题。

当我看这段代码时，我立刻想到 O(n)for 循环但是行

result = result * k

让我觉得这是不同的东西。

if power(int n, int k)
{
    int result = n
    for (int i = 1; i < n; i++){
        result = result * k
    }
}

只是寻找一些关于为什么我可能错或不错的明确解释

Answer 1

这不是一个棘手的问题，除非你使用像 C++ 这样允许运算符重载的语言，并且 k 或 result 类型的 operator*() 方法是重载，或者有一个独立的(免费的)重载运算符方法，以这些类型作为其参数定义。我假设情况并非如此，所以:

您的循环的阶数为 O(n)。在那个循环中，你做什么？你做另一个循环吗？或者调用这样做的方法？否。您系统的乘法运算符复杂性是否基于其操作数的大小？也许在技术上是的，因为 32 位乘法在 32 位内核上比 64 位乘法更快，但这是基于操作数的类型，而不是操作数的值。乘法运算通常是 O(1) 阶。

所以整体复杂度是 O(n*1)，或者只是 O(n)。

除了 O(n) 之外，唯一的方法是重载乘法运算符，并以一种天真的方式实现；例如如果它通过迭代 k 次并将 result 添加到自身 k 次来执行整数乘法。 在那种情况下，整体复杂度为 O(n²)。

但在任何正常情况下，复杂度仅为 O(n)。