当前位置: 首页 > 编程日记 > 正文

【每日一学】复杂度分析

文章目录

    • 目标
    • 什么是数据结构
    • 复杂度分析

目标

  1. 建立时间复杂度、空间复杂度意识,写出高质量的代码
  2. 能够设计基础架构
  3. 提高编程技能
  4. 训练逻辑思维

什么是数据结构

广义:一组数据的存储结构 | 操作数据的一种方法
解决问题:如何更快更省的处理数据
量化目标:复杂度分析
在这里插入图片描述

复杂度分析

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

如何分析一段代码的时间复杂度?

  • 仅关心循环执行次数最多的一段代码
  • 加法法则:总复杂度 = 量级最大的那段代码的复杂度
  • 乘法法则:嵌套代码的复杂度 = 嵌套内外代码复杂度的乘积
    在这里插入图片描述

时间复杂度:

  • 常数O(1):无循环、无递归
  • 对数阶O(log n)/O(n log n):归并排序、快速排序
  • O(m+n)、O(m*n):m 和 n 是表示两个数据规模

空间复杂度
在这里插入图片描述

  1. 最好情况时间复杂度
    理想情况
  2. 最坏情况时间复杂度
    最坏情况
  3. 平均时间复杂度
    所有情况加权平均
  4. 均摊时间复杂度
    a. 绝大部分是低级别的复杂度,个别情况是高级别复杂度
    b. 发生具有时序关系
    将个别高级别复杂度均摊到低级别复杂度上
    基本上均摊结果就等于低级别复杂度。

相关文章:

noip2010提高组3题题解 by rLq

本题地址http://www.luogu.org/problem/show?pid1525 关押罪犯 题目描述 S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气…

hdu 1306(字符串匹配)

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid1306 思路&#xff1a;一开始还以为是求最长公共序列呢。。。仔细一看&#xff0c;orz.....就是求两个串匹配时公共部分字符最多相同的个数。。。 View Code 1 #define _CRT_SECURE_NO_WARNINGS2 #include<…

iOS之使用CoreImage进行人脸识别

更新 &#xff1a;应各位朋友的需求&#xff0c;补上了OC版本的demo&#xff0c; OC版下载地址 另外附上 : swift版下载地址 CoreImage是Cocoa Touch中一个强大的API&#xff0c;也是iOS SDK中的关键部分&#xff0c;不过它经常被忽视。在本篇教程中&#xff0c;我会带大家一起…

[HTTP协议]入门篇

文章目录http的前世今生1. 史前时期2. 创世纪3. 从产生到发展HTTP是什么与HTTP相关的各种概念与HTTP相关的技术TCP/IP协议栈http的前世今生 1. 史前时期 20世纪60年代&#xff0c;美国国防部高等研究计划署ARPA建立ARPA网&#xff0c;四个分布在各地的节点20世纪70年代&#…

CSS中实现DIV容器垂直居中

1.vertical-align&#xff1a;middle 垂直对齐 如表格元素中的<td>、<th>、<caption>等&#xff0c;而像<DIV>、<span>这样的元素是没有valign特性的&#xff0c;因此使用vertical-align对它们不起作用。 2.text-align:center 文本水平居中 一、…

如何制作自己的CocoaPod库

作者 OneTea 关注 2016.12.29 18:02* 字数 848 阅读 102评论 0喜欢 6制作流程图&#xff1a; 流程图1.将代码托管在github上 1.1本地代码 如图&#xff1a; Snip20161228_7.png在github上创建 并上传 Snip20161228_3.png切换到本地项目cd xxx路径后 用git命令行 &#xff08;…

【HTTP协议】域名

1. 域名的出现 IP协议将物理网卡的MAC地址抽象转化为4位数字数字化的IP地址对人不友好&#xff0c;需要友好的域名便于人类识别标记 2. 域名的形式 域名是一个有层次的结构——一串用’.分隔的多个单词【主机名.二级域名.顶级域名】最左边是主机名【eg&#xff1a;www提供万…

iOS 多级下拉菜单

前言 App 常用控件 -- 多级下拉菜单, 如团购类, 房屋类, 对数据进行筛选. 有一级, 二级, 三级, 再多就不会以这种样式,呈现给用户了. 作者就简单聊一下 多级下拉菜单 二级下拉筛选菜单.png一 目标 默认显示一个 TableView, 点击数据后, 添加第二个TableView, 并实现大小变化第二…

fork有啥用

#include <stdio.h>#include <sys/types.h>#include <unistd.h>int main(){ pid_t pid1; pid_t pid2; pid1 fork(); pid2 fork(); printf("pid1:%d, pid2:%d\n", pid1, pid2);}输出&#xff1a;pid1:3411, pid2:3412 //父进…

Html Agility Pack基础类介绍及运用

Html Agility Pack 源码中的类大概有28个左右&#xff0c;其实不算一个很复杂的类库&#xff0c;但它的功能确不弱&#xff0c;为解析DOM已经提供了足够强大的功能支持&#xff0c;可以跟jQuery操作DOM媲美&#xff1a;&#xff09; 基础类和基础方法介绍 Html Agility Pack最常…

【Python自动化测试】setuptools

setuptools Python标准的打包分发工具使用简单的setup.py文件&#xff0c;将Python应用打包 最基础的setup.py文件 #!/usr/bin/env python3 # -*- coding: utf-8 -*- from setuptools import setup setup(nameMyDemo, # 应用名version1.0, # 版本号packages[myd…

企业级-Mysql双主互备高可用负载均衡架构(基于GTID主从复制模式)(原创)

前言&#xff1a;原理与思想这里选用GTID主从复制模式Mysql主从复制模式&#xff0c;是为了更加确保主从复制的正确性、健康性与易配性。这里做的是两服务器A,B各有Mysql实例3310&#xff0c;两个实例间互为主从主从复制模式采用GTID主从复制模式&#xff0c;在服务器A,B上配置…

Objective-C自动生成文档工具:appledoc

作者 iOS_小松哥 关注 2016.12.13 15:47* 字数 919 阅读 727评论 10喜欢 35由于最近琐事比较多&#xff0c;所以好久没有写文章了。今天我们聊一聊Objective-C自动生成文档。 做项目的人多了&#xff0c;就需要文档了。手工写文档是一件苦差事&#xff0c;但是我们也有从源码中…

void main()是错的!

很多人甚至市面上的一些书籍&#xff0c;都使用了void main( )&#xff0c;其实这是错误的。C/C中从来没有定义过void main( )。C之父Bjarne Stroustrup在他的主页上的FAQ中明确地写着The definition void main( ) { /* ... */ } is not and never has been C, nor has it even…

Some tips

VScode自动换行 Code -> Perference -> Setting [ “editor.wordWrap”: “on” ]

iOS 自定义转场动画初探

最近项目刚迭代&#xff0c;正好闲下来捣鼓了一下iOS的自定义转场的效果。闲话不多说&#xff0c;直接开始上代码吧。(ps&#xff1a;请忽略实际的转场效果&#xff0c;关注技术本身呢哦。pps&#xff1a;主要是转场的动画做的比较low啦&#xff01;) 1、首先定义一个转场动画的…

Delphi实现WebService带身份认证的数据传输

WebService使得不同开发工具开发出来的程序可以在网络连通的环境下相互通信,它最大的特点就是标准化(基于XML的一系列标准)带来的跨平台、跨开发工具的通用性,基于HTTP带来的畅通无阻的能力(跨越防火墙)。WebService给我们的软件开发带来了诸多好处,但是有一点还是必须要考虑到…

【Linux学习笔记】 - 什么是Linux?

Linux Linux内核 GNU工具 组成部分 Linux内核GUN工具图形化桌面环境应用软件 Linux内核 地位&#xff1a;Linux核心&#xff0c;控制计算机系统上的所有硬件和软件。必要时&#xff0c;分配硬件&#xff0c;并根据需要执行软件 主要功能&#xff1a; a. 系统内存存储 ——…

【转】 Android快速开发系列 10个常用工具类 -- 不错

原文网址&#xff1a;http://blog.csdn.net/lmj623565791/article/details/38965311 转载请标明出处&#xff1a;http://blog.csdn.net/lmj623565791/article/details/38965311&#xff0c;本文出自【张鸿洋的博客】 打开大家手上的项目&#xff0c;基本都会有一大批的辅助类&a…

CollectionView侧滑刷新

作者 SoDoIt 关注 2017.03.05 16:39 字数 33 阅读 31评论 0喜欢 2ABSideRefresh.gif效仿MJRefresh写的侧滑刷新&#xff0c;原理不讲了&#xff0c;需要的直接看代码 GitHub&#xff1a;https://github.com/wangjingyu0018/ABRefresh.git

函数功能MATLAB

近期一直在查找函数功能之类的题问,现在正好有机会和大家享共一下. 百科名片 录目 简介开展程历要主功能新特性版本分析特色优势开展简介开展程历要主功能新特性版本分析特色优势开展编辑本段 简介 matlab开辟任务面界 编辑本段 开展程历 编辑本段 要主功能 1.数值析分 2.数值和…

[HTTP协议]基础篇-待完结

文章目录输入网址后回车输入网址后回车 简单的浏览器HTTP请求过程&#xff1a; 浏览器从地址栏输入中获取服务器IP地址和端口号浏览器用TCP的三次握手与服务器建立连接浏览器向服务器发送拼好的报文服务器收到报文后处理请求&#xff0c;同样拼好报文再发给浏览器浏览器解析报…

IAR之工程配置

参考 : IAR的Workspace顶部下拉菜单中Debug和Release http://blog.csdn.net/yanpingsz/article/details/5588525 最近买了zigbee模块的开发板回来研究, 其中一个实验程序里面有三个版本, 分别是路由/终端/协调器, 忙活了半天不知道同一个project是如何配置成3个不同的版本的. …

CoreText入坑一

CoreText是Mac OS和iOS系统中处理文本的low-level API, 不管是使用OC还是swift, 实际我们使用CoreText都还是间接或直接使用C语言在写代码。CoreText是iOS和Mac OS中文本处理的根基, TextKit和WebKit都是构建于其上。 一. 基础 1.在使用CoreText编写代码之前, 需要先了解一些基…

mysql连接hang住问题分析

【问题现象】&#xff1a; 1. Linuxc多线程连接mysql数据库&#xff0c;每次都是短连接&#xff0c;操作完后就释放连接&#xff0c;有时候会出现mysql_real_connect挂住的现象 2. 挂住超时mysql_real_connect返回后报错如下&#xff1a;Lostconnection to MySQL s…

【Linux学习笔记】 -- 基本Shell命令

常见的目录名均基于文件系统层级标准(filesystem hierarchy standard&#xff0c;FHS) Linux的四个部分&#xff1a; 1 Linux内核&#xff1a;控制所有硬软件&#xff0c;必要时分配硬件根据需要执行软件 系统内存管理&#xff1a;可用物理内存 创建、管理虚拟内存[交换空间…

【OpenCV】图像代数运算:平均值去噪,减去背景

代数运算&#xff0c;就是对两幅图像的点之间进行加、减、乘、除的运算。四种运算相应的公式为&#xff1a; 代数运算中比较常用的是图像相加和相减。图像相加常用来求平均值去除addtive噪声或者实现二次曝光&#xff08;double-exposure&#xff09;。图像相减用于减去背景或周…

简明 Vim 练级攻略(转)

vim的学习曲线相当的大&#xff08;参看各种文本编辑器的学习曲线&#xff09;&#xff0c;所以&#xff0c;如果你一开始看到的是一大堆VIM的命令分类&#xff0c;你一定会对这个编辑器失去兴趣的。下面的文章翻译自《Learn Vim Progressively》&#xff0c;我觉得这是给新手最…

iOS 的离屏渲染

原文链接&#xff1a;http://www.imlifengfeng.com/blog/?p593OpenGL ES 是一套多功能开放标准的用于嵌入系统的 C-based 的图形库&#xff0c;用于 2D 和 3D 数据的可视化。OpenGL 被设计用来转换一组图形调用功能到底层图形硬件&#xff08;GPU&#xff09;&#xff0c;由 G…

MySQL 常见操作指令

什么是SQL&#xff1f; SQL&#xff08;Structured Query Language&#xff09;用于访问和操作数据库的结构化查询语言。 数据库包含一个或多个表&#xff0c;每个表均有名称标识&#xff0c;包含数据的记录&#xff08;行&#xff09;。 典型的SQL语句 1. SELEC语句 SELE…