时间复杂度O
常数时间的操作
一个操作如果和样本数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。
时间复杂度为一个算法流程中,常数操作数量的一个标志。常用大O来表示。具体来说,首先对一个算法流程非常熟悉,然后去写出这个算法流程中,发生了多少常数操作,进而总结出常数操作数量的表达式。
在表达式中,只要高阶项,不要低阶项,也不要高阶的系数,剩下的部分如果为f(N),那么时间复杂度为O(f(N))。
评价一个算法流程的好坏,先看时间复杂度的指标,然后在分拆不同数据样本下的实际运行时间,也就是“常数项时间”。
简单排序算法
选择排序、冒泡排序细节的讲解与复杂度分析(稳定)
时间复杂度O(N^2),额外空间复杂度O(1)
选择排序源码分析:(Java)
public class Code01_SelectionSort {
//测试函数
public static void main(String[] args){
int arr[] = {3,1,2,6,7,8};
System.out.print("排序前:");
for (int a : arr)
System.out.print(a);
selectionSoet(arr);
System.out.print("\n排序后:");
for (int a : arr)
System.out.print(a);
}
//选择排序算法
public static void selectionSoet(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for (int i = 0;i < arr.length - 1; i++){ //i ~ N-1
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;
}
}
冒泡排序源码分析:(Java)
public class Code02_BubbleSort {
public static void main(String[] args){
int arr[] = {3,1,2,6,7,8};
System.out.print("排序前:");
for (int a : arr)
System.out.print(a);
bubbleSort(arr);
System.out.print("\n排序后:");
for (int a : arr)
System.out.print(a);
}
//冒泡排序算法
public static void bubbleSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for (int e = arr.length - 1; e > 0; e--){ //0 ~ e
for(int i = 0; i< e ; i++){
if(arr[i] > arr[i + 1]){
swap(arr, i, i+1);
}
}
}
}
// 交换arr的i和j的值
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、0 ^ N = N
2、满足交换律、结合律
- a ^ b = b ^ a
- (a ^ b) ^ c = a ^ (b ^ c)
常见面试题(异或)
- 一个数组中只有一种数出现奇数次,找出这一个数 {3,3,2,2,7,8,7}
- 一个数组中只有两种数出现奇数次,找出这两个数{3,3,2,7,8,7,8,9,2,10}
异或题解源码实现(提示:偶数次的异或为0,0与任何数异或为任何数)
public class Code07_EvenTimesOddTimes {
//一个数组里面只有一种数出现奇数次,剩下所有数均出现偶数次,找到这个奇数值
public static void printOddTimesNum1(int[] arr){
int eor = 0;
for (int cur : arr){
eor ^= cur;
}
System.out.println(eor);
}
//一个数组里只有两种数出现奇数次,找到这两个出现奇数次的数
public static void printOddTimesNum2(int[] arr){
int eor = 0;
for (int i = 0; i < arr.length; i++){
eor ^= arr[i];
}
// eor = a ^ b
// eor != 0
// eor必然有一个位置上是1
int rightOne = eor & (-eor + 1); // 提取出最右边的1
int onlyOne = 0; //eor'
for(int cur : arr){
if((cur & rightOne) == 0){
onlyOne ^= cur;
}
}
System.out.println(onlyOne + " " + (eor ^ onlyOne));
}
public static void main(String[] args){
int arrOne[] = {3,3,2,2,7,8,7};
int arrTwo[] = {3,3,2,7,8,7,8,9,2,10};
System.out.print("只有一种数现奇数次:");
printOddTimesNum1(arrOne);
System.out.print("\n只有2种数现奇数次:");
printOddTimesNum2(arrTwo);
}
}
插入排序讲解与复杂度分析(不稳定)
时间复杂度O(N^2),额外空间复杂度O(1)
算法流程按照最差情况来估计时间复杂度(某些数据状况的时间复杂度要优于选择排序和冒泡排序)
插入排序源码分析:(Java)
public class Code03_InsertionSort {
public static void insertionSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
//0~0有序
//0~i有序
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);
}
}
}
//i 和j是一个位置会出错
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];
}
}
网友评论