js算法初窥07(算法复杂度)-阿里云开发者社区

开发者社区> zaking> 正文

js算法初窥07(算法复杂度)

简介:   算法复杂度是我们来衡量一个算法执行效率的一个度量标准,算法复杂度通常主要有时间复杂度和空间复杂度两种。时间复杂度就是指算法代码在运行最终得到我们想要的结果时所消耗的时间,而空间复杂度则是指算法中用来存储的数据结构所占用的空间。
+关注继续查看

  算法复杂度是我们来衡量一个算法执行效率的一个度量标准,算法复杂度通常主要有时间复杂度和空间复杂度两种。时间复杂度就是指算法代码在运行最终得到我们想要的结果时所消耗的时间,而空间复杂度则是指算法中用来存储的数据结构所占用的空间。往往一个时间复杂度比较低的算法拥有着较高的空间复杂度,两者是互相影响的,我们前面讲解数据结构中的一些例子和代码也足以说明这一点。本文会简单介绍一下用于描述算法的性能和复杂程度的大O表示法。

  我们先来看一段简单的代码,来帮助我们理解什么是大O表示法:

function increment(num) {
    return ++num;
}

console.log(increment(1));

  上面的代码声明了一个函数,然后调用它。这样的代码无论我们传入的参数是什么,它都会返回自增后的结果。也就是说该函数的执行时间跟我们传入的参数没有任何关系,执行的时间都是X。因此,我们称该函数的复杂度是O(1),常数的

  我们再来看看前面讲过的顺序搜索算法,我们直接把代码拿过来用就好了。

//顺序搜索
function sequentialSearch(array,item) {
    for(var i = 0; i < array.length; i++) {
        if(item === array[i]) {
            return i;
        };
    };
    return -1;
};

  现在我们假设要搜索的数组是[1,2,3...9,10],然后我们搜索1这个元素,那么在第一次判断时就能找到想要搜索的元素。那么我们这里先假设每执行一次循环的开销是1。那么我们还想搜索11,数组中没有这个元素,sequentialSearch 就会执行十次遍历整个数组,发现没有后返回-1。那么在最坏的情况下,数组的长度大小决定了算法的搜索时间。这样的函数的时间复杂度就是O(n)线性的,这里的n就是数组的长度。

  那么,我们来稍微修改一下sequentialSearch让它可以计算开销:

//顺序搜索
function sequentialSearch(array,item) {
    var cost = 0;
    for(var i = 0; i < array.length; i++) {
        cost++;
        if(item === array[i]) {
            return i;
        };
    };
    console.log(array.length,cost);
    return -1;
};

sequentialSearch([1,2,3,4,5,6,7,8,9,10],11);

  很简单,就是加上了一个cost变量来计数。那么我们下面再来看看冒泡排序的时间复杂度是怎样的,这里我们不再浪费篇幅,直接在代码中加入计数器:

function swap(array,index1,index2) {
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}

function bubbleSort(array) {
    var length = array.length;
    var cost = 0;
    for (var i = 0; i < length; i++) {
        cost++;
        for (var j = 0; j < length - 1; j++) {
            cost++;
            if(array[j] > array[j + 1]) {
                swap(array,j,j+1);
            }
        }
    }

    console.log(length,cost);
}

bubbleSort([2,3,4,1,8,7,9,10]);

  代码本身没什么好说的,我们发现,如果数组的长度是8,那么我们排序所消耗的时间就是64,如果长度是10,消耗的时间就是100。换句话说,冒泡排序的时间复杂度就是数组长度的平方,也就是O(n2)。

<!DOCTYPE html>
<html>
<head lang="en">
    <meta charset="UTF-8">
    <style>
        body { background-color: #DDDDDD; font: 30px sans-serif; }
    </style>
    <script type="text/javascript" src="https://www.google.com/jsapi"></script>
    <script type="text/javascript">
        google.load('visualization', '1.0', {'packages':['corechart']});
google.setOnLoadCallback(drawChart);

function drawChart() {

    var data = new google.visualization.DataTable();
    data.addColumn('string', 'n');
    data.addColumn('number', 'O(1)');
    data.addColumn('number', 'O(log n)');
    data.addColumn('number', 'O(n)');
    data.addColumn('number', 'O(n log n)');
    data.addColumn('number', 'O(n^2)');
    data.addColumn('number', 'O(2^n)');

    for (var i = 0; i <= 30; i++) {
        data.addRow([i+'', 1, Math.log(i), i, Math.log(i)*i, Math.pow(i,2), Math.pow(2,i)]);
    }

    var options = {'title':'Big O Notation Complexity Chart',
        'width':700,
        'height':600,
        'backgroundColor':{stroke:'#CCC',strokeWidth:1},
        'curveType':'function',
        'hAxis':{
            title:'Elements (n)',
            showTextEvery:5
        },
        'vAxis':{
            title:'Operations',
            viewWindowMode:'explicit',
            viewWindow:{min:0,max:450}
        }
    };

    var chart = new google.visualization.LineChart(document.getElementById('chart_div'));
    chart.draw(data, options);
}
    </script>
</head>
<body>
<div id='chart_div'></div>
</body>
</html>

  上面的代码是用js画的一幅图,其中有一些常用的大O表示法所对应的时间复杂度,大家可以把代码COPY到本地自行去看一下,这样会才会对大O表示法有更好的理解,为了偷点懒,也为了大家可以确实的自己去看一下图标。我这里不会把图给大家贴上的。

  下面给大家贴上几张图,来看看我们之前学习的一些数据结构和算法的时间复杂度是怎样的。

1、常用数据结构的时间复杂度

2、图的时间复杂度

表格中的V代表顶点,E代表边。

3、排序算法

4、搜索算法的时间复杂度

  终于,我们了解了几乎我们前面学过的所有的数据结构和算法的时间复杂度,这样我们在选择算法的时候可以更确切地评估它的效率。

  那么,我们本系列的文章也将告一段落。后面准备深入的学习一下CSS。可能会把其中一些比较有意思的地方贴出来与大家分享。

 

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

  最后,感谢大家的阅读。如果您觉得或许还有那么点用处,可以把我的主页加入你的收藏夹中以便需要的时候可以快速的找到。

一只想要飞得更高的小菜鸟

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10081 0
Bystack的高TPS共识算法
共识算法是分布式系统保证节点数据状态一致性的方法,在区块链的共识算法分POW(工作量证明)和POS(权益证明)两大类。第一类POW模式是在公链项目中运用的最广泛应用的共识算法,比特币长达10年的运行已充分证明POW的安全性与稳定性。
748 0
常用算法和复杂度总结
一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) ...
3176 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2254 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13887 0
+关注
zaking
web前端,vue,小程序
40
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载