首页 文章

算法的最坏情况怎么会有不同的界限?

提问于
浏览
2

我一直试图弄清楚这一点 . 其他一些线程解决了这个问题,但我真的不明白答案 . 还有许多答案相互矛盾 .

我知道算法永远不会超过上限,永远不会比下限更快 . 但是,我不知道最佳案例时间存在上限,最坏情况时间存在下限 . This question really threw me in a loop.我无法绕过这个...给定的运行时间可以有不同的上限和下限?

例如,如果有人问:“显示大小为n的堆上某些算法的最坏情况运行时间是Big Omega(lg(n))” . 如果给出运行时间,你怎么可能得到一个下限,任何约束?

那么,总之,算法的最坏情况上限可能与最坏情况下限不同?怎么会这样?一旦给出案例,不受限制变得无关紧要吗?尝试独立学习算法,我真的需要首先考虑这个问题 .

5 回答

  • 0

    我接受的那个问题的答案就是一个函数,它的运行时间在n ^ 2和n ^ 3之间振荡,这取决于n是否为奇数 . 我试图提出的一点是,有时形式为O(n ^ k)和Omega(n ^ k)的界限不够充分,即使最坏情况下的运行时间是一个完全明确定义的函数(其中,像所有函数一样,是它自己最好的下限和上限) . 这种情况发生在更自然的函数,如n log n,对于k≤1而言是Omega(n ^ k)但不是O(n ^ k),而对于k,则是O(n ^ k)而不是Omega(n ^ k)> 1(因此不管我们如何选择常数k),因此不是Theta(n ^ k) .

  • 0

    假设您编写这样的程序来查找整数的最小素因子:

    function lpf(n):
      for i = 2 to n
        if n%i == 0 then return i
    

    如果您在数字10 ^ 11 3上运行该功能,则需要10 ^ 11 2步 . 如果你在数字10 ^ 11 4上运行它只需要一步 . 因此,函数的最佳情况时间是O(1)步,其最坏情况时间是O(n)步 .

  • 0

    Big O表示法,通常基于输入数据集的大小来描述运行时迭代中的效率 . 符号以最简单的形式编写,忽略倍数或添加剂,但保持指数形式 . 如果您有 O(1) 的操作,它将在恒定时间内执行,无论输入数据如何 .

    但是,如果您有 O(N)O(log(N)) 之类的内容,它们将根据输入数据以不同的速率执行 .

    高限和低限分别描述算法可以采用的最大和最小迭代 .

    示例: O(N) ,上限是最大输入数据,下限最小 .

    额外来源:Big O Cheat SheetMIT Lecture Notes

    更新:看看上面提到的Stack Overflow问题,该算法分为三个部分,它有3种可能的运行时类型,具体取决于数据 . 现在真的,这是三种不同的算法,旨在处理不同的数据值 . 算法通常仅用效率的一种表示法进行分类,并且该表示法对于所有可能的N值都花费最少的时间 .

    O(N^2) 的情况下,较大的数据将呈指数级增长,而较小的数字将快速进行 . 该算法确定数据集的运行速度,但是根据算法设计要处理的数据范围给出界限 .

  • 0

    我将尝试在quicksort算法中解释它 . 在快速排序中,您有一个数组并选择一个元素作为数据透视表 . 下一步是将输入数组分成两个数组 . 第一个将包含元素<pivot和第二个元素> pivot . 现在假设您将在已排序的列表上应用quicksort,并且pivot元素将始终是数组的最后一个元素 . 分区的结果将是一个大小为n-1的数组和一个大小为1的数组(pivot元素) . 这将导致运行时间为O(n * n) . 现在假设pivot元素将始终将数组拆分为两个大小相等的数组 . 在每个步骤中,阵列大小将被切成两半 . 这将导致O(n log n) . 我希望这个例子能让你对此更加清楚 . 另一种众所周知的排序算法是mergesort . Mergesort总是运行时为O(n log n) . 在mergesort中,你将向下切割数组,直到只留下一个元素并将爬上调用堆栈以合并一个大小的数组,然后合并大小为2的数组,所以上 .

  • 0

    假设您使用数组实现了一个集合 . 要插入元素,只需将其放入下一个可用存储桶即可 . 如果没有可用的存储桶,则会增加数组的容量 m .

    对于插入算法 "there is no enough space" 是更糟糕的情况 .

    insert (S, e)
       if size(S) >= capacity(S) 
         reserve(S, size(S) + m)
       put(S,e)
    

    假设我们从不删除元素 . 通过跟踪最后一个可用位置, putsizecapacity 在空间和内存中是 Θ(1) .

    reserve 怎么样?如果它像[realloc in C] [1]那样实现,在最好的情况下,你只需在现有内存的末尾分配新内存(保留的最佳情况),或者你也必须移动所有现有元素(更糟的情况)保留) .

    • worst case lower bound for insert is the best case of reserve() ,如果我们不挑剔则在 m 中是线性的 . insert 在最坏的情况下是空间和时间的 Ω(m) .

    • worst case upper bound for insert is the worse case of reserve() ,在 m+n 中是线性的 . insert 在最坏的情况下是空间和时间的 O(m+n) .

相关问题