zgsla’s Blog

一、先介绍一下mysql事务隔离级别的几个相关的概念。 1、脏读（Dirty Read）： 脏读是读到了其他事务回滚前的脏数据。比如事务B执行过程中修改了数据X，在未提交前，事务A读取了X，而事务B却回滚了，这样事务A就形成了脏读。 2、不可重复读（Nonrepeatable Read）： 读到了其他的事务已提交的数据（不可重复读的重点是修改），事务A查询了一条数据后，事务B对该条数据进行修改，此时当事务A再次查询该数据时，得到的结果与第一次查询的不一致。 3、幻读（Phantom Read）： 读到了其他事务已提交的数据（幻读的重点在于新增或者删除），当事务A第一次读取某个范围记录后，事务B新增了一条记录，事务A在此读取这个范围是会多一条记录导致幻读出现。 二、mysql事务隔离级别 1、读未提交（Read Uncommitted）： 顾名思义，事务A可读取到其他事务未提交的内容，在此级别下脏读、幻读、不可重复读等问题都会出现。 2、读已提交（Read Committed）： 大多数数据库默认的事务隔离机制，解决了脏读的问题，仍存在幻读和不可重复读。 3、可重复读（REPEATABLE READ）： InnoDB引擎的默认事务隔离级别，解决了脏读和不可重复读的问题，但仍然存在幻读的问题。InnoDB和Falcon存储引擎通过多版本并发控制（MVCC，Multiversion Concurrency Control）机制解决了该问题。 4、可串行化（SERIALIZABLE） 最高的隔离级别，它通过强制事务排序，使之不可能相互冲突，从而解决幻读问题。简言之，它是在每个读的数据行上加上共享锁，后面的事务需要等待前面事务提交或者rollback。在这个级别，可能导致大量的超时现象和锁竞争。

问题 求斐波那契数列第$10^{19}$项的值，由于结果巨大，输出$mod$ $1000000007$的结果即可。 定义 前两项为1，从第三项开始都满足下面的公式 $$k_n = k_{n-1} + k_{n-2}$$ $$1,1,2,3,5,8,13\ldots$$ 简单的python实现 def fib(n): a = 0 b = 1 for _ in range(n): a, b = b, a + b return a 可以看出，上面算法的时间复杂度是$O(n)$，可以说是比较优的方式了，但是当我在我的电脑上运行上面的代码求第$10^{19}$次项的值时，它很久都没有给我运行结果。 需要使用到斐波那契Q矩阵来减少运算次数 先介绍一下快速幂运算的概念 $x^2 = x × x$ $x^4 = x^2 × x^2$ $x^{100} = x^{64} × x^{32} × x^4$ 观察上面的等式，$x^4$的计算如果用一次项乘4次需要计算3次，但是如果先计算2次项的平方则只需要计算2次。 同理，求$x^n$只需要计算$log2^n$次（实际操作是将低次项的结果保留起来，计算高次项时利用低次项的结果作为基础 ） 同时， $mod$运算也满足 $(A×B)\%C=(A\%C)×(B\%C)$ 使用幂运算的规则，所以只需要找到一个数或者表达式 $A$ 满足： $$k_n = A × k_{n-1}$$ 那么求第$n$项$fibonacci$值的问题就可以转化成求 $A^{n-1}$的问题了 但是通过$fibonacci$数列的定义可以知道，仅已知$k_{n-1}$无法确定$k_n$的值，必须要同时已知$k_{n-1}$和$k_{n-2}$才能确定$k_n$的值，即无法找到到 $A$ 满足$k_n = A × k_{n-1}$...

排序算法是《数据结构与算法》中最基本的算法之一。 十大经典排序算法对比 排序算法 时间复杂度 空间复杂度 排序方式 稳定性 平均 最好 最坏 冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 内部排序 :heavy_check_mark: 选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 内部排序 :x: 插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 内部排序 :heavy_check_mark: 希尔排序 $O(n^{1.3})$ $O(n)$ $O(n^2)$ $O(1)$ 内部排序 :x: 归并排序 $O(n\log_2n)$ $O(n\log_2n)$ $O(n\log_2n)$ $O(n)$ 外部排序 :heavy_check_mark: 快速排序 $O(n\log_2n)$ $O(n\log_2n)$ $O(n^2)$ $O(n\log_2n)$ 内部排序 :x: 堆排序 $O(n\log_2n)$ $O(n\log_2n)$ $O(n\log_2n)$ $O(1)$ 内部排序 :x: 计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(k)$ 外部排序 :heavy_check_mark: 桶排序 $O(n+k)$ $O(n+k)$ $O(n^2)$ $O(n + k)$ 外部排序 :heavy_check_mark: 基数排序 $O(n×k)$ $O(n×k)$ $O(n×k)$ $O(n + k)$ 外部排序 :heavy_check_mark: 详细说明及代码实现如下：...

使用 hugo 设置我的博客 1、简单 2、方便 3、快速 今天使用hugo上线了我的博客了