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

Question

关闭。这个问题需要更多focused。它当前不接受答案。

---

是否要改善此问题？更新问题，使其仅按editing this post专注于一个问题。

[<5小时前关闭。

[有人可以解释以下函数的时间复杂度（大符号），它是我仍然难以理解并帮助理解它的一个话题，请谅解

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

Answer 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) - 1，len(preferences)，这使时间复杂度为O（len（products）^ 2 * len（preferences））

Answer 2

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

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

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

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

Answer 3

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

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