算法时间与空间复杂度求解咨询：含三个算法实例疑问

分析f1的时间复杂度 #

先看你的f1函数：

def f1(x):
    m = len(x)
    found = False
    while m>=1:
        c = m - m/3*3
        if c==1:
            found=True
        m = m/3

这里的循环每次把m除以3，直到m < 1停止。假设初始m = n，那么循环执行的次数是满足n/(3^k) >=1的最大整数k，也就是k = log₃n（取上整）。每次循环里的操作都是O(1)的，所以时间复杂度是Θ(log₃n)，也就是Θ(log n)（因为对数的底数在大O表示里可以忽略，常数系数不影响）。你之前想的Θ(n/3)是错的，因为这里不是线性遍历，而是每次规模折减为1/3，属于对数级别的循环。

分析f2的时间复杂度 #

再看f2：

def f2(x):
    found = False
    n = len(x)-1
    while n!=0 and not found:
        if x[n]==7:
            found=True
        else:
            n=n-1
    return found

你的判断是对的，时间复杂度是Θ(n)。最好情况是第一次就找到7，时间O(1)；最坏情况是遍历到最后一个元素（或者直到n=0），需要执行n次循环，每次循环O(1)操作。而Θ表示的是紧界，这里最坏情况是Θ(n)，平均情况也是线性的，所以整体时间复杂度可以描述为Θ(n)（通常复杂度分析默认看最坏情况）。

分析f3的时间复杂度 #

接下来是f3，这是一个递归分治函数：

def f3(x,i,j):
    if (i<j-1):
        k1 = (j-i+1)/3
        k2 = 2*k1
        f3(x,i,i+k1)
        f3(x,i+k1+1,i+k2)
        f3(x,i+k2+1,j)
        for k in range(i,j):
            print x[k]
    else:
        print x[i]

我们可以用递归式来推导。设问题规模为n = j - i + 1，当n <=2时（i >= j-1），执行O(1)的打印操作；当n>2时，递归调用3个规模为n/3的子问题，然后执行一个O(n)的循环（遍历i到j-1，共n-1次操作，属于O(n)）。

所以递归式是：
T(n) = 3*T(n/3) + O(n)

用主定理（Master Theorem）来解这个递归式：主定理的情况2，当a=3，b=3，f(n)=n，此时log_b a = log₃3 =1，而f(n)=Θ(n^1)，满足情况2的条件，所以T(n)=Θ(n log n)。

简单解释一下：每次递归把问题分成3个1/3规模的子问题，然后合并步骤（打印）是线性的，所以整体复杂度是线性对数级。

计算算法复杂度的通用方法 #

没有绝对通用的公式，但有一些通用的思路和工具：

• 循环类算法：数循环执行的次数，看每次循环的操作复杂度，然后相乘。注意循环的终止条件，如果是每次规模折减（比如除以2、3），那就是对数级；如果是每次减1，就是线性级；如果是每次平方增长，就是根号级，以此类推。
• 递归类算法：写出递归式，然后用主定理、递归树法或者代入法求解。主定理适合大部分分治类的递归，递归树可以直观看到每层的复杂度总和，代入法需要猜测复杂度然后验证。
• 摊还分析：如果有一些操作偶尔耗时高，但整体平均下来有规律，可以用摊还分析（比如动态数组的扩容操作）。
• 最坏情况/平均情况：通常默认分析最坏情况，除非题目特别说明平均情况。

另外，记住几个常见的复杂度级别：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)，这些是复杂度增长的大致顺序。

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