Можно ли уменьшить временную сложность с O (n ^ 2) до O (n)? - PullRequest
Новая
       5

Можно ли уменьшить временную сложность с O (n ^ 2) до O (n)?

0 голосов
/ 07 октября 2019

У меня есть последовательность A 1 , A 2 , A 3 ..... A N . Для каждого действительного i count value элемента A i - это число действительных индексов j < i, таких что A j делится на A i .

Я хочу знать максимум count value.

Я сделал это, используя следующий код: 

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))

Пример ввода: 

1
7 
8 1 28 4 2 6 7

Пример выходных данных: 

3

Объяснение:

A 5 = 2 делит 4, 28 и 8, поэтому его значение счетчика равно 3В count_arr нет элемента с более высоким значением счетчика.

Сложность по времени будет O (n 2 ). Я хочу знать, можно ли решить эту проблему быстрее, возможно, с помощью сложности O (n).

1 Ответ

1 голос
/ 07 октября 2019

Если у вас есть простой способ выяснить, каковы делители числа, вам нужно пройти через вашу последовательность только один раз: 

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))

Это торгует за время, которое требуется, чтобы найти делители каждого числа по сравнению со временем, которое требуется дляпроверить каждый элемент против всех предыдущих элементов.

...