科学知识：时间复杂度计算方法

一、定义

（1）如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。我们常用大O表示法表示时间复杂性，称之为大O记法。
（2）一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。常见的时间复杂度高低顺序如下：
O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < O(2^n) < O(n!) < O(n^n)

二、时间复杂度计算步骤

⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。

三、时间复杂度计算规则

（1）对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
（2）对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
（3）对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
（4）对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))
（5）对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

赞 (0)

相关推荐

  • 科学知识：时间复杂度计算方法

    一.定义 (1)如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的"时间复杂性".我们常用大O表示法表示时间复杂性,称之为大O记法. (2)一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法.常见的时间复杂度高低顺序如下: O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n

  • 科学知识：理解socket

    网络上的两个程序通过一个双向的通信连接实现数据的交换,这个连接的一端称为一个socket. Socket的英文原义是"孔"或"插座".作为BSD UNIX的进程通信机制,取后一种意思.通常也称作"套接字",用于描述IP地址和端口,是一个通信链的句柄,可以用来实现不同虚拟机或不同计算机之间的通信.在Internet上的主机一般运行了多个服务软件,同时提供几种服务.每种服务都打开一个Socket,并绑定到一个端口上,不同的端口对应于不同的服务.Soc

  • 科学知识：同步、异步、阻塞和非阻塞区别

    简单点说: 阻塞就是干不完不准回来,一直处于等待中,直到事情处理完成才返回: 非阻塞就是你先干,我先看看有其他事没有,一发现事情被卡住,马上报告领导. 我们拿最常用的send和recv两个函数来说吧... 比如你调用send函数发送一定的Byte,在系统内部send做的工作其实只是把数据传输(Copy)到TCP/IP协议栈的输出缓冲区,它执行成功并不代表数据已经成功的发送出去了,如果TCP/IP协议栈没有足够的可用缓冲区来保存你Copy过来的数据的话...这时候就体现出阻塞和非阻塞的不同之处了:

  • 科学知识：二进制、八进制、十进制、十六进制转换

    一. 十进制与二进制之间的转换 (1) 十进制转换为二进制,分为整数部分和小数部分 ① 整数部分 方法:除2取余,逆序排列,即每次将整数部分除以2,余数为该位权上的数,而商继续除以2,余数又为上一个位权上的数,这个步骤一直持续下去,直到商为0为止,最后读数时候,从最后一个余数读起,一直到最前面的一个余数.下面举例: 例:将十进制的168转换为二进制 得出结果 将十进制的168转换为二进制,(10101000) 第一步,将168除以2,商84,余数为0. 第二步,将商84除以2,商42余数为0.

  • PHP小程序自动提交到自助友情连接

    PHP小程序自动提交到自助友情连接

    目前网络上有一种ASP程序的自助友情连接联盟很流行,这个程序需要填写自己网站的标题.网址.邮箱.简介等内容然后提交,并且在自己网站做好该联盟的链接``并且点一次,就可以自动审核通过了. 不过,按照常规的方法,一个小时也登陆不了几个自助友情连接联盟,有什么省时省力的方法呢? 看了下这个ASP程序的代码 自己动手写了一个PHP的自动提交程序.程序包含两个文件,我分别取名为 1.php link.php(这个可以随意修改) 1.php代码: 复制代码 代码如下: <form id="form1&

  • 六一国际儿童节 儿童节的由来

    国际儿童节 国际儿童节(又称儿童节,International Children's Day)定于每年的6月1日. 它是为了保障世界各国儿童的生存权.保健权和受教育权,抚养权,为了改善儿童的生活,为了反对虐杀儿童和毒害儿童而设立的节日.目前世界上许多国家都将6月1日定为儿童的节日. 节日由来 国际儿童节的设立,和发生在二战期间一次著名的屠杀有关.1942年6月,德国法西斯枪杀了捷克利迪策村16岁以上的男性公民140余人和全部婴儿,并把妇女和90名儿童押往集中营.村里的房舍.建筑物均被烧毁,好端端

  • 2008大学生入党申请书 模板

    敬爱的党组织:  我叫 ,男, 族,现年 岁,我志愿加入中国共产党,愿意为共产主义事业奋斗终身.我衷心地热爱党,她是中国工人阶级的先锋队,是中国各族人民利益的忠实代表,是中国社会主义事业的领导核心.中国共产党以实现共产主义的社会制度为最终目标,以马克思列宁主义.毛泽东思想.邓小平理论为行动指南,是用先进理论武装起来的党,是全心全意为人民服务的党,是有能力领导全国人民进一步走向繁荣富强的党.她始终代表中国先进生产力的发展要求,代表中国先进文化的前进方向,代表中国最广大人民的根本利益,并通过制定正确

  • c++ KMP字符串匹配算法

    目录 KMP算法简介 前缀表 如何构造前缀表next数组 如何用next数组进行模板匹配 总结 KMP算法简介 KMP算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,它主要的思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配. 本章以力扣 28. 实现 strStr()为例子进行讲解. 力扣28.实现strStr()函数:给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 n

  • 高级前端面试手写扁平数据结构转Tree

    目录 前言 什么是好算法,什么是坏算法 时间复杂度 计算方法 空间复杂度 计算方法: 不考虑性能实现,递归遍历查找 不用递归,也能搞定 最优性能 小试牛刀 前言 招聘季节一般都在金三银四,或者金九银十.最近在这五六月份,陆陆续续面试了十几个高级前端.有一套考察算法的小题目.后台返回一个扁平的数据结构,转成树. 我们看下题目:打平的数据内容如下: let arr = [ {id: 1, name: '部门1', pid: 0}, {id: 2, name: '部门2', pid: 1}, {id:

  • 基于python批量处理dat文件及科学计算方法详解

    摘要:主要介绍一些python的文件读取功能,文件内容修改,文件名后缀更改等操作. 批处理文件功能 import os path1 = 'C:\\Users\\awake_ljw\\Documents\\python for data analysis\\test1' path2 = 'C:\\Users\\awake_ljw\\Documents\\python for data analysis\\test2' filelist = os.listdir(path1) for files i

随机推荐