python - 用函数变换集合的高效算法

标签 python algorithm function python-3.x

我正在编写一段代码,用于计算下面函数 g(x) 中相对于自然数的间隙,然后对它们求和。

from math import *

a = set()
n = eval(input("n = "))

def g(x):
    return floor(x*log10(x))   # thanks to tzaman

b = 1
while g(b) < n:
    a.add(g(b))
    b+=1

aprime = set(range(max(a)))

z = max(a)

print(z*(z+1)/2-sum(a))        # thanks to tzaman

input("Done!")

我试图让 n = 10 ** 10,即 10000000000,并在合理的时间内(例如 < 10 分钟)执行计算。然而,这段代码的执行时间长得可笑,我想知道:是否有更有效的方法来做到这一点?


I/O 示例

n = 12, output = 15

其他信息

下图比较了xg(x):

 x   | 1 2 3 4 5 6 7 8 9 10 11 12
g(x) | 0 0 1 2 3 4 5 7 8 10 11 12

集合x\g(x)表示x中而不是g(x)中的成员,并且对于以下数字12、{0,6,9};它们的总和是 15。因此,当 n = 12 时,output = 15

最佳答案

您的麻烦可能来自于 sum(aprime-a) 行。这迫使 python 计算两个集合的集合差。考虑到您的集合有多大,这会极大浪费时间。

请注意,当 ba 的子集时,sum(a-b) = sum(a)-sum(b)(如这是你的情况)。所以我们现在有 sum(aprime)-sum(a)

接下来利用 aprime 只是一个算术序列这一事实!你有一个公式来计算这些东西的总和!您可以代替 sum(aprime)

maxVal = max(a)
sumAPrime = ((maxVal +1)*maxVal)/2

所以您现在有了 sumAPrime - sum(a) 作为您的解决方案!

我将假设您需要优化才能适用于任何任意函数 g,因此您不能对代码中的函数做出假设。

希望这有帮助! :)

关于python - 用函数变换集合的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31973507/

相关文章:

python - 将已知位置的原始日期时间转换为 UTC 日期时间

python - 分别安装 Python 2 和 3

c - 如何从带有指针的函数返回数组

javascript - JS - 在外部函数之外声明嵌套函数

python - Django 身份验证 : password change template customization

python - Django q 更新一个已经安排好的任务

algorithm - +ve 和 -ve nums 的拆分数组

c++ - 当算法放置在循环内部时,它会产生不同的结果,C++

java - 在递归算法中计算运行时间

javascript - HTML 内联 javascript 函数不起作用