В чем заключается неэффективность моего алгоритма?

Question

Имеется вот такая задача:

Дано натуральное число n (1 ≤ n ≤ 10^18). Найдите количество пар неотрицательных целых чисел (x, y), удовлетворяющих соотношению x^2 + y^3 = n. В ответе укажите одно число – количество пар.

Ограничение по времени для Python - 5 секунд, по памяти - 256 мб. Для других языков 1 секунда, память - 64 мб.

Вот код:

n, count = int(input()), 0

def X_square(N):
    array = []
    for i in range(N + 1):
        fig = i ** 2
        if fig <= N:
            array.append(fig)
        else:
            break
    return array


def N_sub_Y_cube(N):
    for j in range(N + 1):
        fig = j ** 3
        if fig <= N:
            yield N - fig
        else:
            break


def binary_search(elem, array):
    lower_bound = 0
    upper_bound = len(array) - 1
# count = 0

    while lower_bound <= upper_bound:
        center = (lower_bound + upper_bound) // 2
        if elem == array[center]:
            # count += 1
            return elem
        elif elem < array[center]:
            upper_bound = center - 1
        elif elem > array[center]:
            lower_bound = center + 1
    return -1


for i in N_sub_Y_cube(n):
    if binary_search(i, X_square(n)) == -1:
        continue
    else:
        count +=1
print(count)

Для 10^9 работает вполне нормально, но потом упирается в ограничение по времени (для 11 значного числа уже считает долго). И правильно ли я понимаю, что сложность О(nlogn)?

Answer 1

Идите по y от 1 до 10^6 (корень кубический из n), вычисляйте x, убеждайтесь, что это целое или нет... Примерно так (в Python могу и ошибиться...)

import math

n, count = int(input()), 0

for y in range(n + 1):
    x = n - y * y * y
    if x < 0:
        break
    z = int(math.sqrt(x))
    if z * z == x:
        count += 1

print(count)

БЛОГ НА HUSL

В чем заключается неэффективность моего алгоритма?

Ответы (1 шт):