精选文章 复杂度分析--整理

复杂度分析--整理

作者:weixin_38168786 时间: 2021-02-05 10:06:40
weixin_38168786 2021-02-05 10:06:40
【摘要】一、时间复杂度 
  
  复杂度量级  粗略地可以分为多项式量级和非多项式量级。其中,非多项式量级只有两个: 
 我们把时间复杂度为非多项式量级的算法问题叫作 NP(Non--Deterministic Polynomial,非确定多项式)问题。 
 1. O(1) 
  1  int i = 8;
2  int j = 6;
3  int sum = i + j; 
  
 一般情况下,...

一、时间复杂度

复杂度分析--整理1

 复杂度量级  粗略地可以分为多项式量级和非多项式量级。其中,非多项式量级只有两个:复杂度分析--整理2

我们把时间复杂度为非多项式量级的算法问题叫作 NP(Non--Deterministic Polynomial,非确定多项式)问题。

1. O(1)

1  int i = 8;
2  int j = 6;
3  int sum = i + j;

一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是O(1)。

2. O(logn)、O(nlogn)

1  i=1;
2  while (i <= n)  {
3 i = i * 2;  
4  }

复杂度分析--整理3

  只要知道 x 值是多少,就知道这行代码执行的次数了,这段代码的复杂度就是复杂度分析--整理4

1  i = i * 2;
2  i = i * 3;
3  .
4  .
5  .
6  i = i * 100;

复杂度分析--整理5等于 复杂度分析--整理6,O(Cf(n)) = O(f(n)),统一表示为 O(logn)。 

循环执行 n 遍,时间复杂度就是 O(nlogn)。

比如,归并排序、快速排序的时间复杂度都是 O(nlogn)。

3. O(m+n)、O(m*n)

加法法则:如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么  T(n)=T1(n)+T2(n)=max(O(f(n)), 

乘法法则:如果 T1(n)=O(f(n)),T2(n)=O(g(n));那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).

代码的复杂度由两个数据的规模来决定,无法事先评估 m 和 n 谁的量级大:

修改加法法则为:T1(m) + T2(n) = O(f(m) + g(n))。 乘法法则继续有效:T1(m)*T2(n) = O(f(m)* f(n))。

二、空间复杂度

时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。

类比一下,空间复杂度全称就是渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度就是 O(1)、O(n)、O(n2 )

复杂度分析--整理7

 三、最好最坏情况时间复杂度

最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。

最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。

 1 // n 表示数组 array 的长度
 2 int find(int[] array, int n, int x) {
 3   int i = 0;
 4   int pos = -1;
 5   for (; i < n; ++i) {
 6 if (array[i] == x) {
 7 pos = i;
 8 break;
 9  }
10   }
11   return pos;
12 }

平均情况时间复杂度:

有 n+1 种情况:在数组的 0~n-1 位置中和不在数组中,每种情况下,查找需要遍历的元素个数累加起来,

然后再除以 n+1,得到需要遍历的元素个数的平均值,

复杂度分析--整理8

时间复杂度的大 O 标记法中,可以省略掉系数、低阶、常量。简化之后,得到的平均时间复杂度就是 O(n)。

考虑概率进去如下:

假设在数组中与不在数组中的概率都为 1/2。另外,要查找的数据出现在 0~n-1 这 n 个位置的概率也是一样的,为 1/n。

复杂度分析--整理9

 

 这个值就是概率论中的加权平均值,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

去掉系数和常量,这段代码的加权平均时间复杂度仍然是 O(n)。

四、均摊时间复杂度

平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景比它更加特殊、更加有限。

 

转载于:https://www.cnblogs.com/zhangji0522/p/11505214.html

勿删,copyright占位
您找到想要的结果了吗?
复杂度分析--整理
提交成功!非常感谢您的反馈,我们会继续努力做到更好
分享文章到微博
分享文章到朋友圈

上一篇:NIOS生成Nios libaray

下一篇:MongoDB数据库常用SQL命令 — MongoDB可视化工具Robo 3T

您可能感兴趣

  • 设计模式之单例模式+LayoutInflater分析

    单例模式 单例模式是应用最广的模式之一,在应用这个模式时,单例对象的类必须保证只有一个实例存在,许多时候整个系统只需要拥有一个全局变量,这样有利于我们协调系统整体的行为定义:确保某一个类只有一个实例,而且自行实例化并...

  • Stratum 矿池协议实例分析

    原文地址:https://steemit.com/cn/@speeding/stratum-pool-protocol 最近在VPS上搭建unomp矿池,主要参考的文档是官网上的README,遇坑无数,以后有机会再专门写一篇。在最后一步测试矿工与矿池之间能否正常完成挖矿工作时,需要了解一些stratum这个协议的细节。 当前的主流挖矿协议是stra...

  • bind-9.3.2 源码 分析

     iso_copy_out_to_desktop.pl "sdb1:\sdb1\all_chm\linux_src_chm_1.iso\\_xfile_2010_06\\bind-9.3.2.chm" root/bin/named/main.c     ns_os_init(program_name);     dns_res...

  • Hessian源码分析(三)------ HessianSkeleton

    HessianSkeleton是Hessian server端的核心类,主要功能是接收网络输入流(被包装为AbstractHessianInput),反序列化输入流得到methodName和参数,然后调用服务端的服务,得到结果后序列化为输出流,返回给客户端,主要流程如下图所示: HessianSkeleton的核心代码如下所示: public...

  • 【整理】结合div 给flash添加链接

    背景说明: 项目中,曾有一个需求,给flash广告添加链接,跳转到另一个网站。于是直接在html的flash object前面加上<a href="url">,发现链接不起作用。    解决方案: 以下各种尝试的解决方案,方式三为最佳实践!   【方式一】在flash外围添加 <a href=...

  • MediaPlayerService分析

    一.MediaPlayerService简介 1.Media Service的启动 Media进程定义: service media /system/bin/mediaserver     class main     user media     group audio camera inet net_bt net_bt_admin n...

  • Hadoop开发者1-4期打包整理下载,需要的赶紧(附内容说明,先看后下)

    内容说明: Hadoop开发者第一期 1 Hadoop 介绍 2 Hadoop 在国内应用情况 3 Hadoop 源代码 eclipse 编译教程 7 在 Windows 上安装 Hadoop 教程 13 在 Linux 上安装 Hadoop 教程 19 在 Windows 上使用 eclipse 编写 Hadoop 应用程序 24 在 Window...

  • MySQL慢查询的两种分析方案 slow sql

    前一段日子,我曾经设置了一次记录在MySQL数据库中对慢于1秒钟的SQL语句进行查询。想起来有几个十分设置的方法,有几个参数的名称死活回忆不起来了,于是重新整理一下,自己做个笔记。   对于排查问题找出性能瓶颈来说,最容易发现并解决的问题就是MySQL慢查询以及没有得用索引的查询。   OK,开始找出MySQL中执行起来不“爽”的SQL语...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。
复杂度分析--整理介绍:华为云为您免费提供复杂度分析--整理在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多复杂度分析--整理的相关内容。| 移动地址: 复杂度分析--整理 | 写博客