如果我的函数有两个嵌套的for循环,它是否以二次时间运行?

2024-03-28 09:31:53 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在学习用大O符号分析算法。我通过Ranum&;米勒的Problem Solving with Algorithms in Python textbook。其中一项任务如下:

Write two Python functions to find the minimum number in a list. The first function should compare each number to every other number on the list. 𝑂(𝑛2). The second function should be linear 𝑂(𝑛).

没有指导或解决方案,所以我是盲目的。以下是我对二次函数和线性函数的解:

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
        for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number


def find_min_linear(a_list):
    return min(a_list)

我的逻辑是,有两个nester for循环在问题a_list上迭代,这将给我O(n^2)运行时间。而对于第二种解决方案,我只是调用内置函数min(),这样应该有线性时间?(虽然现在我认为这可能意味着它有固定的时间?)

我最初误读了作业中的“查找列表中的最大数”,因此我也为max_number.编写了这些函数。我遵循了与min_number.相同的逻辑。如上所述,我对二次和线性时间的理解和实现正确吗

def find_max_quadratic(a_list):
    max_number = None
    for a_number in a_list:
        for item in range(len(a_list)):
            if a_number > a_list[item]:
                max_number = a_number
    return max_number


def find_max_linear(a_list):
    return max(a_list)



Tags: to函数innumberforreturndef时间
3条回答

您的逻辑是正确的,您分析自己实现的方法的方式正是应该如何实现的

可能让人困惑的是第二个,在这种情况下,您调用的是一些函数,这些函数已经在语言库中实现了。这也有自己的复杂性,在这个例子中是O(n)

如果您想使自己的方法具有线性复杂性,则可以通过以下方式实现:

  1. 定义最小变量
  2. 循环遍历数组,并将循环中的值与定义的最小值进行比较
  3. 如果最小值>;循环值,然后将其重新分配给最小值

您分析和计算算法复杂性的逻辑是正确的。然而,我怀疑你的老师可能不喜欢你写的代码

线性函数的问题

def find_min_linear(a_list):
    return min(a_list)

您被要求编写一个函数,返回列表的最小值,为此,您。。。使用python内置函数返回列表的最小值

这对于任何实际应用都是一个好主意,因为python内置函数可能比您自己编写的任何函数都要快;您可以相信它没有bug,而不是浪费时间检查您自己的代码是否有bug

但是你的老师可能更感兴趣的是你提出了一个求最小值的算法,而不是你知道已经有一个python内置函数可以做到这一点。min函数确实是线性的,但是这个函数的存在只是因为有人能够首先提出一个线性算法,并用它来实现这个函数 . 事实上,我觉得很令人不安的是,你的老师没有明确禁止你在这个作业中使用python内置的minmax。如果我是一名学生,我可能会提到内置函数存在并以线性时间执行,然后我会编写自己的函数而不使用现有函数

二次函数的问题

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
        for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number

从技术上讲,你的函数是有效的,它是二次函数。然而,内部for循环很麻烦。变量item从未使用过;它的唯一目的是确保循环有n个迭代(其中n是列表的长度)。循环体将始终执行完全相同的操作;if中的条件要么总是true,要么总是false;如果它是真的,那么min_number = a_number将一次又一次地将相同的值写入相同的变量

换句话说:在for循环中重复执行这个if语句毫无意义;只要执行一次

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
    #    for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number

Tadaaaaaa!只需少一行,算法仍能正确执行并返回列表的最小值

该算法现在是线性的,而不是二次的。你的老师要你做一个二次算法。您可能认为可以添加一个for循环,使您的算法具有二次性。这在技术上是正确的,但是下面的算法也可以工作:

def find_min_quadratic(a_list):
    min_number = find_min_linear(a_list)
    for item in range(len(a_list)**2):
        beebboop = 57
    return min_number

毫无疑问,这个函数是二次函数——我们明确地包含了一个运行n^2次迭代的循环。但是你的老师可能觉得你在取笑他们

此外,如果你仔细阅读,你的作业文本上会说“第一个函数应该将每个数字与列表中的其他数字进行比较。”。你的二次函数没有这样做

二次算法

您已经找到了一个线性算法(通过从二次函数中删除一行),所以现在您仍然需要找到一个二次函数。这有点违反直觉,就我个人而言,我非常不喜欢这个任务。编写算法通常遵循以下步骤:

  1. 表达问题
  2. 找到一个算法来解决这个问题
  3. 分析算法的复杂性
  4. 找到一种新的算法,以较低的复杂度解决问题

因此,按照这些思路进行的任务将非常有意义:

  1. 编写一个函数来查找列表的最小值
  2. 分析函数的复杂性
  3. 如果你的函数不是线性的,那么写一个新函数来寻找线性时间内列表的最小值

如果你已经找到了线性函数,那么寻找一个效率较低的函数是很尴尬的,这导致你添加了一个for循环,它无缘无故地浪费了时间

我认为赋值的目的不是人为地制造一个效率较低的函数,而是尝试提出一个完全不同的算法,然后理解它并非所有的算法都同样有效

您的老师明确地说:“第一个函数应该将每个数字与列表中的其他数字进行比较。”。所以我们可以用它来编写一个新函数:

def find_min_quadratic(a_list):
    # ...
    for a in a_list:
        # ...
        for b in a_list:
            if a > b:
                # ...
        # ...

尝试填充空格,使其返回最小值。您可以添加其他变量,也可以添加其他if语句,但不能添加其他for循环。提示:如何确定元素a是否为最小值?由于for b in a_list循环,我们能否找到a是否是最小值

二次解如下所示:

def findMinQuad(aList):
    overallmin = alist[0]
    for i in aList:
        issmallest = True 
        for j in a List: 
            if i > j:
                issmallest = False
        if issmallest: 
                overallmin = i 

    return overallmin

因为我们用嵌套的for循环在输入列表上迭代了两次,所以我们知道答案是二次时间O(n^2)。嵌套循环还确保我们将每个数字与列表中的其他数字进行比较

线性解决方案如下所示:

def findMinLin(aList):
    minsofar = aList[0]
    for i in aList:
        if i < minsofar:
            minsofar = i
    return minsofar

这是一个非常不言自明的例子,我们假设第一个数字是最小的,然后我们迭代列表,看看是否找到一个较小的数字。如果我们这样做了,那么这个数就是新的最小数,在循环结束时,任何保存为最小数的东西,实际上都是最小数

相关问题 更多 >