时间戳

首页 > 解决方案 > isPascal() 方法的时间复杂度是多少

performance - isPascal() 方法的时间复杂度是多少

问题描述

static int isPascal(int n) {
    int sum = 0;
    int nthVal = 1;
    while (sum < n) {
        sum = sum + nthVal;
        nthVal++;
    }
    return sum == n ? 1 : 0;
}

这里函数检查给定数字是否为帕斯卡数。帕斯卡数是一个数字，它是一些 i 从 1 到 i 的整数之和。

例如6 是帕斯卡数，因为 6 = 1 + 2 + 3

这个函数的时间复杂度是多少？会是 O(logn) 时间吗？如果是这样，这里的日志基础是什么？

标签： performancefunctiontime-complexity

解决方案

如果您考虑计算平方根 O(1) 操作，您可以在 O(1) 中进行此检查，借助前 i 个自然数之和的公式

sum(i) = (i^2 + i)/2

现在在你的情况下你不知道i但你知道sum(i)，因为那是n你想要检查它是否是帕斯卡数。所以你有了

n = (i^2 + i) /2

或者

i^2 + i - 2n = 0

用相应的公式求解这个二次方程给出

i = -1/2 + sqrt(2*n + 1/4)

你可以放弃这个方程的第二个解，因为i它必须> 0是一个有效的解。如果结果i是整数，n则为帕斯卡数。否则不是。

从该公式也可以看出，您的迭代解决方案在 O(sqrt(n))

推荐阅读