首页
精选文章时间复杂度查看全文时间复杂度是计算机科学对程序耗时的一种衡量手段，时间复杂度通用使用O符号来表示，其衡量纬度通常使用输入数据的长度，最终写成O(f(n))。数据复杂度中的大O用来表示算法时间复杂的渐近上界，因为对于同一个算法，在不同的输入情况下，计算的次数会存在较大的差异，例如插入排序，在数据有序的情况下其时间复杂度是O(n)，但是在数据无序的情况下，其时间复杂度是会O（n2），所以我们提到插入排序其时间复杂度是O（n2）。 快速排序在数据逆序的情况下时间复杂度是O（n2），但是平均情况下，快速排序的时间复杂度是O（n*log（n））。O表达的近似复杂度一般情况描述的更加偏向一般情况下的时间复杂度，而不是严格的上界。 除了O之外，还有下列符号也是描述时间复杂度的符号； Θ，表示准确的时间复杂度，即时间复杂度的上界下界(tight) ο，表示算法复杂度的上界(not tight)，例如快速排序的上界时间复杂度是o（n2）。 Ω，表示渐进下界，该复杂度是最优情况下的近似复杂度。 ω，表示下界，表示最优情况下严格的时间复杂度。 常用的时间复杂度有O（n3）、O（n2）、O（n*log（n））。 时间复杂度在计算过程中，去忽略常数项系数，该常数项系数是指所有低于最高阶项的计算因子。 常见的计算项的阶度高低如下： O（2n）> O（n3）> O（n2）> O（n*log（n））> O（n）> O（log（n））> O（1）ConcurrentHashMap【Java】查看全文HashMap是Java中最经常使用的Hash表，但是其是线程不安全的集合类，在并发场景下数据会出现脏读等，而且头插法实现的HashMap在rehash阶段还可能导致死循环，Java中并发安全的Hash表一般有三种方式：Collections.synchronizedMap(Map)、HashTable以及ConcurrentHashMap。ConcurrentHashMap的存储结构和HashMap基本一致，也是数组+链表+红黑树进行存储。 不同的是，ConcurrentHashMap为了保证线程安全，采取了很多技术手段。 线程安全 JDK1.8对ConcurrentHashMap的实现进行了较大大改造。 在JDK1.7及以前，ConcurrentHashMap采用Segment分段锁的机制，对整个数组进行分段，每段都是由HashEntry对象连接而成的链表，称为Segment。 每个分段都有一个单独的锁，Segment分段锁，分段锁继承自ReentrantLock，其同步机制只会对一个分段生效，不同数据段之间的数据不会存在竞争关系，从而提高了并发的访问率。 ConcurrentHashMap在JDK1.8中取消了Segment分段锁机制，采用Node+CAS+Synchronized实现线程安全。 在数据写入时，没有Hash冲突直接通过CAS乐观锁机制进行加入，写入失败进行自旋。如果存在 Hash 冲突，就通过加锁的方式进行插入，从而保证线程安全。（如果是链表就按照尾插法插入，如果是红黑树就按照红黑树的数据结构进行插入）； 初始化 ConcurrentHashMap用于存储数据的数组在进行初始化时通过自旋锁…Docker查看全文Docker是一个用Golang语言实现的开源项目，通过Docker可以将程序以及程序依赖的环境以及组件都打包到容器（Docker Container）。Docker可以屏蔽底层硬件的差异，Docker的配置文件Dockerfile可以在不同的操作系统，不同的硬件平台实现快速打包部署等功能。 Docker最初是dotCloud公司的内部项目，dotCloud公司在2008年由Kamel Founadi、Sebastien Pahl共同创建，目标是利用容器技术方便构建"大规模的创新工具"。 2013年3月20日，dotCloud发布了Docker的首个版本，并将其开源。此项技术能够将Linux容器中的应用代码打包并轻松的在服务器之间迁移。2013年3月25日dotCloud加入linux基金会。docker官方博客提到，docker使用了许多linux社区开发的软件和技术，因此linux社区的发展和壮大对docker来讲也是非常重要的。 2013年9月，红帽公司成为Docker的主要合作伙伴，利用Docker来支撑其OpenShift云业务。随后，谷歌、亚马逊以及DigitalOcean也迅速的在其云服务平台提供了Docker的支持。主流云厂商的加入，加速了Docker的发展进度。同年12月底，DotCloud Inc则更名为Docker Inc，全力推进Docker的研发工作。 2014年6月的DockerCon大会上Docker正式发布了Docker 1.0 版本。会议上同时发布Docker Image的镜像仓库Docker Hub。同样在2014年6月，基于google公司的Borg系统的Kubernetes发布。 2015年6月… |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库精选内容 |
