[数据结构与算法]左神算法-基础01

左神算法-基础01

认识时间复杂度

常数时间的操作 ：一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。

在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那么时间复杂度为O(f(N))。

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行 时间，也就是**“常数项时间”。**

选择排序、冒泡排序细节的讲解与复杂度分析

时间复杂度O(N^2)，额外空间复杂度O(1)

	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;	//记录最小值位置
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;	//改变最小值位置
			}
			swap(arr, i, minIndex);	//交换最小值到前面 	
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int e = arr.length - 1; e > 0; e--) {
			for (int i = 0; i < e; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);	//把较大数交换到后面
				}
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
        //只有i，j两个位置不同时可以这么写
        //否则会将数据抹成0
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

插入排序细节的讲解与复杂度分析

时间复杂度O(N^2)，额外空间复杂度O(1)

算法流程按照最差情况来估计时间复杂度

	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

二分法的详解与扩展

1）在一个有序数组中，找某个数是否存在

2）在一个有序数组中，找>=某个数最左侧的位置

3）局部最小值问题

	public static boolean exist(int[] sortedArr, int num) {
		if (sortedArr == null || sortedArr.length == 0) {
			return false;
		}
		int L = 0;
		int R = sortedArr.length - 1;
		int mid = 0;
		while (L < R) {
			mid = L + ((R - L) >> 1);
			if (sortedArr[mid] == num) {
				return true;
			} else if (sortedArr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return sortedArr[L] == num;
	}

	// 在arr上，找满足>=value的最左位置
	public static int nearestIndex(int[] arr, int value) {
		int L = 0;
		int R = arr.length - 1;
		int index = -1;
		while (L < R) {
			int mid = L + ((R - L) >> 1);
			if (arr[mid] >= value) {
				index = mid;
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return index;
	}

	//找到一个局部最小值就返回，	会优先找到左边的	
	public static int getLessIndex(int[] arr) {
		if (arr == null || arr.length == 0) {
			return -1; // no exist
		}
		if (arr.length == 1 || arr[0] < arr[1]) {
			return 0;
		}
		if (arr[arr.length - 1] < arr[arr.length - 2]) {
			return arr.length - 1;
		}
		int left = 1;
		int right = arr.length - 2;
		int mid = 0;
		while (left < right) {
			mid = (left + right) / 2;
			if (arr[mid] > arr[mid - 1]) {
				right = mid - 1;
			} else if (arr[mid] > arr[mid + 1]) {
				left = mid + 1;
			} else {
				return mid;
			}
		}
        //left == right 此时的	left 就是下一次的mid
		return left;
	}

异或运算的性质与扩展

1. 0^N == N N^N == 0
2. 异或运算满足交换律和结合率
3. 不用额外变量交换两个数
4. 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数
5. 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数

	//找一个出现了奇数次的数
	public static void printOddTimesNum1(int[] arr) {
		int eO = 0;
		for (int cur : arr) {
			eO ^= cur;
		}
		System.out.println(eO);
	}
	//找两个出现了奇数次的数
	public static void printOddTimesNum2(int[] arr) {
		int eO = 0, eOhasOne = 0;
		for (int curNum : arr) {
			eO ^= curNum;
		}
		int rightOne = eO & (~eO + 1);	//提取最右边的1出来
		for (int cur : arr) {
            //当这个数的最右边一位1 与rightOne 相同时，才将它异或进去
			if ((cur & rightOne) != 0) {
				eOhasOne ^= cur;
			}
		}
		System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
	}

对数器的概念和使用

1. 有一个你想要测的方法a
2. 实现复杂度不好但是容易实现的方法b
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
5. 如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a 或者方法b
6. 当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

	// for test	已知正确的方法
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	// for test	构造一个随机的数组
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test	拷贝一个数组
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test	判断两个数组的数据是否相同
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test	打印数组
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test	指定测试次数，数据范围，---》进行测试
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			insertionSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");

		int[] arr = generateRandomArray(maxSize, maxValue);
		printArray(arr);
		insertionSort(arr);
		printArray(arr);
	}

剖析递归行为和递归行为时间复杂度的估算

用递归方法找一个数组中的最大值，系统上到底是怎么做的？

master公式的使用

T(N) = a*T(N/b) + O(N^d)

1. log(b,a) > d -> 复杂度为O(N^log(b,a))
2. log(b,a) = d -> 复杂度为O(N^d * logN)
3. log(b,a) < d -> 复杂度为O(N^d)