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。可能会把其中一些比较有意思的地方贴出来与大家分享。

 

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

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

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

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

相关文章
Bystack的高TPS共识算法
共识算法是分布式系统保证节点数据状态一致性的方法,在区块链的共识算法分POW(工作量证明)和POS(权益证明)两大类。第一类POW模式是在公链项目中运用的最广泛应用的共识算法,比特币长达10年的运行已充分证明POW的安全性与稳定性。
736 0
数据结构面试之十二——排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)
十一、数据结构面试之十二——排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)
6 0
算法时间复杂度
算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算不太精确的。只能依据统计方法对算法进行估算。
477 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2198 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
3971 0
JAVA并发处理经验(四)并行模式与算法6:socket的服务端多线程
一、前言 关于网络编程,这一章一般用NIO编程,但是我们得一步步,免得扯着蛋蛋。我们先温习一下,socket的服务器---客户端;我们适用服务端用线程池,线程池没有懂得小火炮,看以前的,或者直接问群里就ok。
725 0
Hacker News 排名算法工作原理
这篇文章我要向大家介绍Hacker News网站的文章排名算法工作原理,以及如何在自己的应用里使用这种算法。这个算法非常的简单,但却在突出热门文章和遴选新文章上表现的异常优秀。
13 0
利用Clion对几种排序算法进行时间复杂度与空间复杂度的分析
算法 利用算法解决问题的步骤: 1、将问题模型化 2、找到一个合适的算法 3、这个算法足够快吗?对空间友好吗 4、如果不是,找出为什么 5、找到一个方法解决这个问题 6、一直迭代直到这个问题被解决 ...
979 0
+关注
zaking
web前端,vue,小程序
32
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载