时间复杂度能从O（n^2）降到O（n）吗？

Question

我有一个序列a₁，a₂，a₃…a_N。对于每个有效的i，元素A_i的count value是有效索引j < i的数目，使得A_j可被A_i整除。你知道吗

我想知道最大值。你知道吗

我使用以下代码：

for _ in range(int(input())):             #number of test cases
    n = int(input())                      # no. of elements in A  
    A = list(map(int, input().split()))
    count_arr = []                      # array with count value
    for i in range(n):
        b = A[:i]
        b = [x%A[i] for x in b]
        count_arr.append(b.count(0))
    print(max(count_arr))

Sample Input:

1
7 
8 1 28 4 2 6 7

Sample Output:

3

Explanation:

A₅ = 2 divides 4, 28 and 8, so its count value is 3. There is no element in count_arr with a higher count value.

时间复杂度为O（n²）。我想知道这个问题能否以更快的方式解决，也许是O（n）复杂度。你知道吗

Answer 1

如果你有一个简单的方法来找出一个数的除数，你只需要遍历你的序列一次：

def divisors(num):
    yield 1

    for i in range (2, int(num ** .5) + 1):
        if num % i: # not divisible
            continue 
        yield i
        if i**2 != num:
            yield num // i

是一种相当幼稚的求数除数的方法。你知道吗

如果还需要包含原始数字，可以将divisors更改为

def divisors(num):
    yield 1
    if num == 1:
        return
    yield num
    for i in range (2, int(num ** .5) + 1):
        if num % i: # not divisible
            continue 
        yield i
        if i**2 != num:
            yield num // i

然后需要一个结构来保存每个除数已经被看到的时间。对于这个目的，collections.Counter是理想的选择

def previous_multiples(sequence):
    counter = Counter()
    for i in sequence:
        yield counter[i]
        counter.update(divisors(i))

这就得出了每个数之前有多少个数可以被它整除。然后它用自己的除数更新除数

这可以这样叫max(previous_multiples(sequence))

这就权衡了查找每个数字的除数所需的时间与检查每个元素与之前所有元素所需的时间。你知道吗