时间戳

首页 > 解决方案 > 在这个特定示例中，如何将 O(n^2) 算法转换为 O(n)？

python - 在这个特定示例中，如何将 O(n^2) 算法转换为 O(n)？

问题描述

我正在尝试解决我为练习技能而进行的编码练习。它涉及为篮球运动员提取一些 .JSON 数据。我的程序必须找到所有可能的玩家对，它们的总和等于给定的整数输入。

这是我设计的代码：

import json
import requests

def to_number(A):
    
    B = int(A)
    
    return B
        

def search(Number):
    response = requests.get("https://mach-eight.uc.r.appspot.com/")

    data = json.loads(response.text)
    PLAYERS = data["values"]

    answer_list = []

    for player1 in PLAYERS:
    
        raw_height = player1['h_in']
        height_1 = to_number(raw_height)
    
        PLAYERS.remove(player1)
        for player2 in PLAYERS:
        
            raw_height = player2['h_in']
            height_2 = to_number(raw_height)
        
            result = height_1 + height_2
        
            if result == Number:
                par = (player1['first_name'] + ' ' + player1['last_name'] + ' & ' + 
                       player2['first_name'] + ' ' + player2['last_name'])
            
                answer_list.append(par)
        
    return answer_list

def executer():
    Number = int(input("insert your integer: "))
    result = search(Number)
    
    return result
    
if __name__=="__main__":
    
    result = executer()
    stop_here = len(result)
    
    while stop_here == 0:
    
        print("No matches found, please try with a new number \n\n")
    
        result = executer()
        stop_here = len(result)
        
    print(result)

到目前为止，它确实完成了查找对的目标，但是以嵌套 for 循环为代价，我需要想出一种减少计算时间的方法，例如，作为 O(n) 算法。

到目前为止，我尝试过使用 itertools 包和置换函数制作没有循环的对，但我很快意识到这只会让它变慢。

另一方面，我考虑将玩家的每个高度减去整数输入，这将返回与初始高度配对的唯一可能高度：

图形示例

这种方法会直接引导我找到唯一可能的配对，对吧？但是我在这之后该怎么做有问题。我不确定如何仅通过一个循环来确定与操作结果高度相对应的玩家。

如果你能帮助我解开这个难题，我将非常感激。同样，如果您能想到另一种方法，我全是耳朵和眼睛。

标签： pythonalgorithmoptimization

解决方案

首先：因为所需的输出必须包含与所需高度总和匹配的所有对，所以任何算法的最坏情况复杂度至少为 O(²)。举个例子，所有玩家的身高都是 70，而函数的参数是 140，那么很明显你必须输出所有可能的对。其中有 (-1)/2 个，即 O(²)。由于算法必须产生那么多对，因此它至少要执行那么多步骤，因此它至少是 O(²)。我在这里忽略了人名中的字符数。我将假设这些名称最多有 100 个字符，因此这不会影响时间复杂度。

但是，在查看平均和最佳情况时间复杂度时，您的算法并不是最优的，因为您的算法仍然是 O(²)，而可以在 O() 的最佳情况时间复杂度下完成：

您可以使用以高度为键的字典，并将具有相同高度的人员列表（他们的全名）作为值。

这是您的函数的外观：

def search(total):
    response = requests.get("https://mach-eight.uc.r.appspot.com/")

    data = json.loads(response.text)
    players = data["values"]

    d = defaultdict(list)
    for player in players:
        d[int(player['h_in'])].append(player['first_name'] + " " + player['last_name'])

    return [player + " & " + other
        for height in d
            if total - height in d
                for other in d[total - height]
                    for player in d[height]
                        if player < other
    ]

因此，例如，如果输入中没有高度相同的玩家，那么该算法将在线性时间内完成这项工作。

推荐阅读