复杂度与简单排序算法

前置知识点的学习

计算机逻辑运算

  • 与 ：当所有输入条件同时满足1，输出1；输入条件只要有0就输出0。java : &
  • 或：输入条件有1即输出1；一个1也没有才输出0。java : |
  • 非：输出结果与输入条件取反。0变1，1变0。 java : !
  • 异或：仅当两输入取不同的值时异或结果为1；否则均为0。java : ^ 可以理解为无进位加法

异或的规则: 1. 0^N= N N^N=0 2. 符合交换律和结合率 AB=BA  (AB)B=A(BC)

通过异或运算交换两个变量的值

如果a和b指向同一个内存会导致N^N=0，而出现问题，在平时不推荐使用。

1
2
3
4
5
6
7
8
9
10
11
12
public class main{

    public static void main(String[] args) {
        int a = 234;
        int b = 349;
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("a:"+a+" "+"b:"+b);
    }
}
//运行结果为a:349 b:234

复杂度计算

  以冒泡排序为例：冒泡排序每次循环所用的时间分别为 1n-1,1n-2,1-n3,…,12。为一个d为1的等差数列 则这个算法的时间消耗为Sn=n*a1+n(n-1)d/2去掉常数和低次幂的数只保留最高次幂的数 结果为O(n²)。 > 时间复杂度按算法的最坏情况记。例：插入排序最好情况O(N)，最坏情况O(N²)。

提取出一个二进制数最右的一个1所在的位置

变量名二进制数

常见排序算法时间复杂度和空间复杂度