算法之时间复杂度简析 前言 最近准备对算法进行一些系统的总结和学习，不积跬步无以至千里,不积小流无以成江海.此文主要对时间复杂度进行简单梳理和个人总结，本人才疏学浅，有所疏漏在所难免，如有不当和错误之处，欢迎指正 时间复杂度的定义（Time Complexity） 时间复杂度，用简单地话描述为：为了大概估算程序运算时间的一种概量。那用什么来估算的呢？用简单的程序执行代码的次数，如int a = 3执行一次，一个n此的for循环表示执行n次等等。广义的T（n）表示在一个完全理想状态的计算机中程序所执行的实际指令次数，下面会提到的O（n）大O（Big Oh），Ω(omega)，Θ(Theta) 都是对T（n）的一个大略估算抽象而来，这里先说明一下个人理解的精确度大小为：T(n)>Θ(Theta)...阅读全文
hashset底层为hashmap。 源码如下： /** * Constructs a new, empty set; the backing HashMap instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() { map = new HashMap<>(); } 默认 initial capacity（hashmap底层数组大小）为16，load factor 为 0.75 add() 方法 /** * Adds the specified element to this set if it is not already present. * Mo...阅读全文
提一下哈希表，看下百科： 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。 简单理解：1.通过某种算法（使用key的hash算法）,计算出key的磁盘散列值，优点为速度和易用。 2.hashmap底层实现仍为数组（HashMap 底层就是一个数组结构，数组中的每一项又是一个链表。数组每个元素里存的是链表的表头信息，有了表头就可以遍...阅读全文
前言 本文只作一些概念性说明，后续会整理每种排序算法的具体实现。个人知识和能力有限，搜集整理和理解可能不到位，如有错误，欢迎指正 插入排序原理 跑n-1趟，对于p=1到N-1趟，插入排序保证从位置0到位置p（数组也是从0开始计算）的数据是有序的，从后面每次拿一个数组往前面插，找到有序的位置（如此时51为被插入数，则在34到64之间）。需要使用两次for循环，时间复杂度为O（n^2） 希尔排序原理（缩减增量排序） 简单粗暴 计算效率取决于选择的缩减增量序列，只要序列最后最小的为1，任何增量序列都是可行的。最坏时间复杂度为n^2，而使用2^k-1的Hibbard增量序列的最坏运行事件为N^1.5 堆（优先队列）排序原理 堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节...阅读全文
引言： 1. 给定一个整数，依次打印其没每位上的数字 想法： 1. 把数字转为String,再转为char，最后放入char[]，逐个打印 2. 递归 代码: package com.anteoy.dataStructuresAndAlgorithm.javav2; /** * Created by zhoudazhuang on 17-2-16. * Description: */ public class PrintString { public static void main(String [] args) { printStrs(123456789); printByte(123456); printString(123456); } /** * 逐个字符打印所给整数 * @par...阅读全文
Kafka对于producer发来的消息怎么保证可靠性？ 每个partition都给配上副本，做数据同步，保证数据不丢失。 副本数据同步策略 和zookeeper不同的是，Kafka选择的是全部完成同步，才发送ack。但是又有所区别。 所以，你们才会在各种博客看到这句话【kafka不是完全同步，也不是完全异步，是一种ISR机制】 这句话对也不对，不对也对（谜语人......） 首先笔者认为：Kafka使用的就是完全同步方案。 完全同步的优点 同样为了容忍 n 台节点的故障，过半机制需要 2n+1 个副本，而全部同步方案只需要 n+1 个副本， 而 Kafka 的每个分区都有大量的数据，过半机制方案会造成大量数据的冗余。（这就是和zookeeper的不同） 完全同步会有什么问题？ 假设就有这么...阅读全文
