時間複雑度再学習
時間複雑度再学習
1.認識時間の複雑さ
定数時間の操作:1つの操作がデータ量と関係がなければ、毎回一定時間内に完了する操作を定数操作と呼ぶ.時間複雑度はアルゴリズムフローにおける定数動作数の指標である.O(big Oと読む)で表されることが多い.具体的には、定数動作数の式では、高次項、低次項、高次項の係数が不要であれば、残りの部分をf(N)と記すと、時間複雑度はO(f(N))となる.アルゴリズムの流れの良し悪しを評価し,まず時間の複雑さの指標を見てから,異なるデータサンプルの下での実際の運転時間,すなわち定数項時間を分析する.
時間の複雑さはデータ規模にも関係しており,2つのアルゴリズムがあれば優劣が見られ,サンプル量も考慮する必要がある.
データフローが決定されたため、挿入ソートはデータ規模に関係し、好ましくはo(N)であり、すべて順序がある.
2.対数器の概念と使用
0、測定したい方法がありますa.
1,絶対的に正しいが複雑度が悪い方法bを実現する.
2、ランダムサンプル発生器を実現する.
3,ペアリングを実現する方法.
4,方法aと方法bを何度も比較して方法aが正しいかどうかを検証する.
5.比較エラーが発生したサンプルがある場合、印刷サンプルはどの方法でエラーが発生したかを分析する.
6.サンプルの数が多い場合、比較テストは依然として正確であり、方法aが正しいと判断できる.
package basic_class_01;
import java.util.Arrays;
public class Code_00_BubbleSort{
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) {
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
//unsigned int a=60; //0011 1100
// unsigned int b=13; //0000 1101
// a=a^b; //a=a^b=0011 0001
// b=a^b; //b=a^b=0011 1100 b1=(a^b)^b
// a=a^b; //a=a^b=0000 1101 a1=(a^b)^((a^b)^b
}
//for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
//for test
public static int[] generateRandomArray(int maxSize,int maxValue) {
//Math.random()->double[0,1）;
//(int)((size+1）*Math.random（）） —>[0,size]
//size=6;size+1=7;
//Math.random()->[0,1)*7->[0,7)double
//double->int[0,6]->int
//
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=10;
int maxValue=100;
boolean succeed=true;
for(int i=0;i<testTime;i++) {
int [] arr1=generateRandomArray(maxSize,maxValue);
int[] arr2=copyArray(arr1);
bubblesort(arr1);
comparator(arr2);
if(!isEqual(arr1,arr2)) {
succeed=false;
break;
}
}
System.out.println(succeed?"nice":"Fucking");
int[] arr=generateRandomArray(maxSize,maxValue);
printArray(arr);
bubblesort(arr);
printArray(arr);
}
}
3.再帰行為と再帰行為の時間複雑度の推定を分析する
再帰的な行動の例
再帰関数は、システムがスタックを圧縮し、サブプロシージャを呼び出すときにスタックを圧縮し、その後、サブプロシージャが値を返し、スタックを弾き、現場を復元し、任意の再帰動作を非再帰動作に変更することができます.
マスター式の使用T(N)=a*T(N/b)+O(N^d)(分割されたサブ問題の規模は毎回同じ)
例えば、T(n)=T(n/5)+T(2/3 n)+o(n^2)はmaster式では使用できません
T(N)サンプル量はNの時間的複雑度であり,aはサブプロセスの発生回数を表し,N/bはサブプロセスのサンプル量を表す.
4.集計ソート
T(n)=2T(n/2)+o(n)->o(n*logn)
package basic_class_01;
import java.util.Arrays;
public class Code_05_MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
// 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);
mergeSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
mergeSort(arr);
printArray(arr);
}
}
5.小和問題と逆順対問題
小和問題と逆順序問題小和問題は1つの配列の中で、各数の左側が現在の数より小さい数を累積して、この配列の小和と呼ばれます.1つの配列の小和を求めます.例:[1,3,4,2,5]1左の方が1より小さい数で、ありません.3左の3より小さい数、1;4左の4より小さい数、1、3;2左の2より小さい数、1;5左の5より小さい数、1、3、4、2;だから小和は1+1+3+1+3+4+2=16
逆順序対問題
1つの配列で、左の数が右の数より大きい場合は、2つの数を折って逆のペアを構成し、すべての逆のペアを印刷します.
package basic_class_01;
import java.util.Arrays;
public class Code_01_InsertionSort {
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];
}
// 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);
}
}