最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 最好时间复杂度、最坏时间复杂度、平均时间复杂度、均摊时间复杂度

    正文概述 掘金(青草酱)   2021-08-01   38

    代码:

    // n 表示数组 array 的长度
    int find(int[] array, int n, int x) {  
        int i = 0;  
        int pos = -1;  
        for (; i < n; ++i) {    
            if (array[i] == x) {      
                pos = i;       
                break;    
            }  
        }  
        return pos;
    }
    

    一、最好时间复杂度

    最好情况就是,arrary数组的第一个元素就是要查找的x,所以最好时间复杂度就是O(1)。

    二、最坏时间复杂度

    最坏的情况就是,这个数组中没有查找的这个元素,那么它会把这个数组遍历一遍,所以最坏时间复杂度是O(n)。

    三、平均时间复杂度

     平均时间复杂度只有在特殊时候才会使用。以上面的代码为例分析:

    一共有n + 1种情况,即从0~n,和不在数组中。

    平均时间复杂度:

    最好时间复杂度、最坏时间复杂度、平均时间复杂度、均摊时间复杂度

    去掉系数、低阶、常数,平均时间复杂度就为O(n)。

    四、均摊时间复杂度

    均摊时间复杂度的情况更特殊,并不常用到。

    思想是:将耗时最多的那次操作均摊到其他耗时最少的操作上。


    起源地 » 最好时间复杂度、最坏时间复杂度、平均时间复杂度、均摊时间复杂度

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元