算法| 再也不怕被问时间复杂度了 (下)

简介: 算法| 再也不怕被问时间复杂度了 (下)

最好情况时间复杂度,最坏情况时间复杂度


我们看一个例子:

// 这段代码是为了在数组中找到n第一次出现的下标
public int find(int[] array, int n) {
    int pos=-1;
    for (int i = 0; i < array.length; i++) {
        if(n==array[i]){
            pos=i;
        }
    }
    return pos;
}

从我们上一章学习的内容我们可以很简单的知道,上面代码的时间复杂度为O(n),数组长度越长,耗时越长。不过很明显,上面的代码可以优化,优化后如下:

public int find(int[] array, int n) {
    int pos=-1;
    for (int i = 0; i < array.length; i++) {
        if(n==array[i]){
            pos=i;
            return pos;
        }
    }
    return pos;
}

我们只需要在找到指定元素后直接结束函数就行了。在这种情况下,我们之前学习的时间复杂度的分析方法已经不适用了。因为我们要查找的元素可能出现在数组中的任意一个元素,甚至在数组中不存在。如果出现在数组中的第一个元素的话,那么时间复杂度就是O(1),但如果在数组中不存在,这种情况下我们需要遍历整个数组,时间复杂度为O(n),所以在不同清空下,这段代码的时间复杂度是不一样的。顾名思义,这段代码的最好情况时间复杂度就是O(1),最坏情况时间复杂度就是O(n),那么平均复杂度又该如何计算呢?不要急,请往下看~


平均情况时间复杂度


如果我们以最好,最坏时间复杂来评判上面的算法的话,很明显是不合理的,因为这两种情况都是在极端情况下才能出现的,这个时候我们需要引入新的评判指标,平均时间复杂度。那么平均时间复杂度又该如何计算呢?要查找的变量有两种情况


1.在数组中。在数组中的话,可能出现在数组的每一个位置上,所以共有array.length中情况

2.不在数组中


假设在数组中跟不在数组中的概率均为二分之一,数组长度为n,那么查找的元素出现在数组中任意位置的概率为:1/2n,那么平均时间复杂度可以这样计算:

image.png

其中1,2…n,代表每种情况下需要遍历的元素的个数,这种情况下平均时间复杂度还是O(n)


了解后我们会发现,平均复杂度的分析相对来说是很复杂的,还要引入概率论的知识。但是在大多数情况下我们不需要区分最好,最坏,平均情况时间复杂度三种情况,很多情况下,我们使用一个复杂度就可以满足需求了。只有同一块代码在不同情况下,时间复杂度有量级的差距,我们才使用这三种复杂度来区分


均摊时间复杂度


我们还是以代码来进行说明:

// 往数组中插入元素,每当数组中元素满了后就将其所有元素置为0
// 不用纠结这种函数有什么用,我们只是用其来说明复杂度相关东西
public void insert(int n) {
    if (count == array.length) {
        for (int i = 0; i < count; i++) {
            array[i]=0;
        }
    } else {
        array[count] = n;
    }
}

在上面的例子中,大多数情况下我们的时间复杂度都是O(1),但是当数组中元素满了后,因为要遍历整个数组,这种情况下时间复杂度为O(n),而且我们可以发现,每n-1次O(1)后,必然伴随着一次O(n)。大家可以思考下,这种情况我们之前说的最好,最坏,平均复杂度分别是多说呢?不难计算分别为,O(1),O(n),O(1)。但是由于上面的算法时间复杂度出现是有规律的,这个时候我们可以引入一个新的概念,即均摊时间复杂度。这样可以帮助我们更好的评判一个算法的优劣。那么均摊时间复杂度该如何计算呢?


我们可以这样思考,每n-1次O(1)的插入之后都会跟着一次O(n)的的插入,那么将耗时多的一次操作均摊到之前的n-1次上,当n趋近无穷大时,该算法的复杂度也就是O(1)了,这就是我们要说的均摊时间复杂度。


总结:


到这里为止,我们就介绍完了各种时间复杂度的概念了。我们需要知道的是,之所以要建立这么多概念是为了更好的对一个算法进行分析,让我们能更全面的分析一个算法的优劣,因为在某些情况下,我们单独依赖于最好,最好,或者平均等时间复杂度进行分析都是不够全面的。



相关文章
|
3月前
|
机器学习/深度学习 缓存 算法
Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【10月更文挑战第4天】在Python编程中,算法的设计与优化至关重要,尤其在数据处理、科学计算及机器学习领域。本文探讨了评估算法性能的核心指标——时间复杂度和空间复杂度。通过详细解释两者的概念,并提供快速排序和字符串反转的示例代码,帮助读者深入理解这些概念。同时,文章还讨论了如何在实际应用中平衡时间和空间复杂度,以实现最优性能。
88 6
|
5月前
|
机器学习/深度学习 算法 程序员
读《趣学算法》:重开算法之门,时间复杂度与空间复杂度
本文是作者阅读《趣学算法》后的笔记,介绍了算法复杂度的基本概念,包括时间复杂度和空间复杂度的不同阶表示,并通过具体例子展示了如何计算和理解算法的效率。
74 2
读《趣学算法》:重开算法之门,时间复杂度与空间复杂度
|
3月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
6月前
|
机器学习/深度学习 存储 算法
颠覆认知!Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【7月更文挑战第22天】在Python算法设计中,时间与空间复杂度是评估算法效能的核心。时间复杂度不仅限于大O表示法,还涵盖平均与最坏情况分析。空间复杂度虽关注额外存储,但也反映内存效率。平衡二者需视场景而定,如利用原地算法减少内存消耗,或牺牲空间加速执行。算法优化技巧,如分治与动态规划,助你在资源与速度间找寻最优解,从而高效应对大数据挑战。
62 3
|
3月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
56 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
3月前
|
存储 算法
算法的时间复杂度和空间复杂度
本文详细讨论了算法的时间复杂度和空间复杂度,包括它们的概念、计算方法和常见复杂度的对比,并通过多个实例解释了如何计算算法的时间和空间复杂度。
231 0
算法的时间复杂度和空间复杂度
|
4月前
|
算法 Python
震惊!Python 算法设计背后,时间复杂度与空间复杂度的惊天秘密大起底!
在 Python 算法设计中,理解并巧妙运用时间复杂度和空间复杂度的知识,是实现高效、优雅代码的必经之路。通过不断地实践和优化,我们能够在这两个因素之间找到最佳的平衡点,创造出性能卓越的程序。
47 4
|
3月前
|
算法 C语言
深入理解算法效率:时间复杂度与空间复杂度
深入理解算法效率:时间复杂度与空间复杂度
|
5月前
|
机器学习/深度学习 存储 算法
算法时间复杂度分析
这篇文章讲解了如何分析算法的时间复杂度,包括关注循环执行次数最多的代码段、总复杂度的确定、嵌套代码复杂度的计算方法,并提供了大O阶的推导步骤和常见时间复杂度的列表,同时还介绍了空间复杂度的概念及其重要性。
|
5月前
|
搜索推荐
九大排序算法时间复杂度、空间复杂度、稳定性
九大排序算法的时间复杂度、空间复杂度和稳定性,提供了对各种排序方法效率和特性的比较分析。
217 1

热门文章

最新文章