滤波函数的时间复杂度是多少? [关闭]

问题描述 投票:-2回答:3
[有人可以解释以下函数的时间复杂度(大符号),它是我仍然难以理解并帮助理解它的一个话题,请谅解

validProductsArray = [] i = 0 j = i + 1 while i < len(products) and j < len(products): if i != j: prodiDominate = 0 prodjDominate = 0 for k in range(len(preferences)): if preferences[k][1] == 1: if products[i][preferences[k][0]] > products[j][preferences[k][0]]: prodiDominate += 1 else: prodjDominate += 1 elif preferences[k][1] == -1: if products[i][preferences[k][0]] < products[j][preferences[k][0]]: prodiDominate += 1 else: prodjDominate += 1 if prodiDominate > prodjDominate: validProductsArray.append(products[i]) j += 1 i += 1 return validProductsArray

python python-3.x list time-complexity big-o
3个回答
1
投票
时间复杂度(大O表示法)表示程序/脚本/函数运行所花费的时间如何演变出参数大小的函数。

例如,一个简单的循环(请参见下面的循环)的时间复杂度为O(nb_cycle),因为运行循环所花费的时间与循环数(nb_cycle)成正比]

for i in range(nb_cycle): print(i)

如果您有嵌套的代码,则时间复杂度会成倍增加。再次使用for循环作为示例(请参见下文),您可以看到print(i, j)被称为nb_cycle * nb_cycle_inner,从而使时间变得复杂:O(nb_cycle * nb_cycle_inner)

for i in range(nb_cycle): for i in range(nb_cycle_inner) print(i, j)

按照此逻辑,您的代码为三个嵌套循环,分别具有长度len(products)len(products) - 1len(preferences),这使时间复杂度为O(len(products)^ 2 * len(preferences))

1
投票
理论上或在纸上的解决方法是找到嵌套循环。在您的情况下,我们有3个,因此粗略估计为O(n ^ 3)。

但是,时间复杂度在很大程度上取决于确定运行时流程的控制语句。

并且按照规则,我们忽略了时间复杂度中的常数和非主导项。

例如如果代码中有两个循环,一个接一个(非嵌套),则为0(2N)。但是去掉2(常数)就变成O(N)。或在O(N ^ 2 + N)的情况下变为O(N ^ 2)。


0
投票
此功能的复杂度为O(Prod^2 * Pref)。验证不是很困难,因为成对的产品循环本身是二次的,并且您遍历所有首选项进行引导。

通常,这种算法不能很好地扩展,特别是当产品数量增加时。

热门问题
推荐问题
最新问题