伪代码时间复杂度这么看

在分析伪代码的时间复杂度时，通常关注循环次数或者递归深度这样的关键操作，因为它们直接影响了算法效率。时间复杂度是用来衡量算法执行速度随着输入规模增长的速度，常用的大O记法（Big O notation）来表示。

例如，如果我们看到这样的伪代码：

for i from 0 to n-1 do
    for j from 0 to n-1 do
        someComputation()
    end
end

这是一个典型的双重循环，每次循环都是`n`次，所以总的时间复杂度是`O(n^2)`，因为它与输入规模`n`的平方成正比。

另外，如果涉及到递归的情况，比如：

function recursiveFunction(n):
    if n <= 1:
        return n
    else:
        return recursiveFunction(n-1) + recursiveFunction(n-2)

这里的时间复杂度是`O(2^n)`，因为每一次函数调用都会生成两个新的调用，直到基本情况为止。

在评估伪代码的时间复杂度时，重要的是识别出核心的操作，并忽略那些与输入无关或对复杂度影响较小的部分。毕竟，我们的目标是理解算法的主要性能瓶颈。

相关问题

最大连续子数组伪代码时间复杂度nlogn

1. 分治算法：

function maxSubarray(A, low, high)
    if high == low
        return (low, high, A[low])
    else
        mid = floor((low + high) / 2)
        (leftLow, leftHigh, leftSum) = maxSubarray(A, low, mid)
        (rightLow, rightHigh, rightSum) = maxSubarray(A, mid + 1, high)
        (crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum
            return (leftLow, leftHigh, leftSum)
        else if rightSum >= leftSum and rightSum >= crossSum
            return (rightLow, rightHigh, rightSum)
        else
            return (crossLow, crossHigh, crossSum)

function maxCrossingSubarray(A, low, mid, high)
    leftSum = A[mid]
    sum = 0
    for i = mid downto low
        sum += A[i]
        if sum > leftSum
            leftSum = sum
            maxLeft = i
    rightSum = A[mid + 1]
    sum = 0
    for j = mid + 1 to high
        sum += A[j]
        if sum > rightSum
            rightSum = sum
            maxRight = j
    return (maxLeft, maxRight, leftSum + rightSum)

时间复杂度：O(nlogn)

2. 分治算法 + 动态规划：

function maxSubarray(A, low, high)
    if high == low
        return (low, high, A[low])
    else
        mid = floor((low + high) / 2)
        (leftLow, leftHigh, leftSum) = maxSubarray(A, low, mid)
        (rightLow, rightHigh, rightSum) = maxSubarray(A, mid + 1, high)
        (crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum
            return (leftLow, leftHigh, leftSum)
        else if rightSum >= leftSum and rightSum >= crossSum
            return (rightLow, rightHigh, rightSum)
        else
            return (crossLow, crossHigh, crossSum)

function maxCrossingSubarray(A, low, mid, high)
    leftSum = A[mid]
    sum = 0
    for i = mid downto low
        sum += A[i]
        if sum > leftSum
            leftSum = sum
            maxLeft = i
    rightSum = A[mid + 1]
    sum = 0
    for j = mid + 1 to high
        sum += A[j]
        if sum > rightSum
            rightSum = sum
            maxRight = j
    return (maxLeft, maxRight, leftSum + rightSum)

function maxSubarrayLinear(A)
    maxSoFar = maxEndingHere = A[1]
    low = maxLow = high = 1
    for i = 2 to length(A)
        if maxEndingHere > 0
            maxEndingHere += A[i]
        else
            maxEndingHere = A[i]
            low = i
        if maxEndingHere > maxSoFar
            maxSoFar = maxEndingHere
            maxLow = low
            high = i
    return (maxLow, high, maxSoFar)

function maxSubarrayHybrid(A, low, high)
    if high - low + 1 <= 128
        return maxSubarrayLinear(A[low...high])
    else
        mid = floor((low + high) / 2)
        (leftLow, leftHigh, leftSum) = maxSubarrayHybrid(A, low, mid)
        (rightLow, rightHigh, rightSum) = maxSubarrayHybrid(A, mid + 1, high)
        (crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum
            return (leftLow, leftHigh, leftSum)
        else if rightSum >= leftSum and rightSum >= crossSum
            return (rightLow, rightHigh, rightSum)
        else
            return (crossLow, crossHigh, crossSum)

时间复杂度：O(nlogn)

大数字乘法分治算法伪代码和时间复杂度分析

大数字乘法的分治算法，也称为Karatsuba算法或二进制拆分法，是一种更高效的传统乘法算法。它的核心思想是将两个大数分成较小的部分，分别进行快速的乘法运算，并通过加法和减法将结果组合起来。

以下是该算法的一个简化版伪代码：

function karatsuba(x, y):
    if x < 10 and y < 10:   // 基本情况，小数乘法
        return x * y
    else:
        n = floor(log2(max(|x|, |y|)))  // 计算最大数的位数
        a = x / 10^(n/2)
        b = x % 10^(n/2)
        c = y / 10^(n/2)
        d = y % 10^(n/2)

        // 递归计算中间值
        z0 = karatsuba(a, c)
        z1 = karatsuba(b, d)
        z2 = karatsuba((a+b), (c+d)) - z0 - z1

        # 返回结果
        return ((z2 * 10^(2*n)) + (z1 * 10^n)) + (z0)

时间复杂度分析：
- 对于每个递归层次，需要进行三个独立的较小尺寸的乘法（z0, z1, z2），每个的时间复杂度为O(n^2)。
- 然后有两次取模和一次除法操作，这些在大多数编程语言中时间复杂度都是常量级别的（O(1)）。
- 因此，总的递归深度为n（取对数次数），所以整个过程的时间复杂度是 O(n^log2(3)) ≈ O(n^1.585)，相比于传统的大数乘法（O(n^2)），这是一个显著的改进。