更新时间:2023-11-28 14:18:22
您的解决方案似乎非常快。在 find_idx
中,你有两个for循环,内部循环可以使用公式进行优化:
Your solution seems quite fast. In find_idx
, you have two for loop, the inner loop can be optimized using the formular:
C(n, k) + C(n-1, k) + ... + C(n-r, k) = C(n+1, k+1) - C(n-r, k+1)
因此,您可以替换 sum(nck(n-2-) x,k-1)for x in range(c-last_c-1))
with nck(n-1,k) - nck(n-c + last_c,k )
。
so, you can replace sum(nck(n-2-x,k-1) for x in range(c-last_c-1))
with nck(n-1, k) - nck(n-c+last_c, k)
.
我不知道你如何实现 nck(n,k)
功能,但它应该是时间复杂度测量的O(k)。在这里,我提供了我的实现:
I don't know how you implement your nck(n, k)
function, but it should be O(k) measured in time complexity. Here I provide my implementation:
from operator import mul
from functools import reduce # In python 3
def nck_safe(n, k):
if k < 0 or n < k: return 0
return reduce(mul, range(n, n-k, -1), 1) // reduce(mul, range(1, k+1), 1)
最后,您的解决方案变为O(k ^ 2)而不递归。这是非常快的,因为 k
不会太大。
Finally, your solution become O(k^2) without recursion. It's quite fast since k
wouldn't be too large.
我注意到 nck
的参数是(n,k)
。 n和k都不会太大。我们可以通过缓存来加速程序。
I've noticed that nck
's parameters are (n, k)
. Both n and k won't be too large. We may speed up the program by caching.
def nck(n, k, _cache={}):
if (n, k) in _cache: return _cache[n, k]
....
# before returning the result
_cache[n, k] = result
return result
在python3中,这可以通过使用 functools.lru_cache $来完成c $ c>装饰者:
In python3 this can be done by using functools.lru_cache
decorator:
@functools.lru_cache(maxsize=500)
def nck(n, k):
...