常用算法时间复杂度

二分查找的时间复杂度为:

首先在n个元素中查找, 然后在n/2个元素中查找, 再在n/4个元素中查找...直到为1, 相当于n经过多少次除以2等于1, 所以其时间复杂度为logN

int binarySearch(int arr[], int target, int n) {
    int left = 0, right = n - 1;
    
    while (left <= right) {
        int pivot = (left + right)/2;
        if (arr[pivot] == target) return pivot;
        if (arr[pivot] < target) left = pivot + 1;
        else right = pivot - 1;
    }
    
    return -1;
}

选择排序: 时间复杂度为O(n^2)

/// 选择排序
/// @param arr 数组
/// @param n 数组长度
void selectionSort(int arr[], int n) {
    int min = 0, tem = 0;
    for (int i=0; i<n; i++) {
        
        min = i;
        
        for (int j=i+1; j<n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        
        if (min != i) {
            tem = arr[min];
            arr[min] = arr[i];
            arr[i] = tem;
        }
        
    }
}

归并排序: 时间复杂度为O(nlogn) 

//合并两个已经排好序的数组
void merge(int array[], int L, int M, int R) {
    
    int LEFT_SIZE = M - L;
    int RIGHT_SIZE = R - M + 1;
    int left[LEFT_SIZE];
    int right[RIGHT_SIZE];

    //左边数组填充数据
    for (int i=L; i<M; i++) {
        
        left[i-L] = array[i];
    }
    
    //右边数组填充数据
    for (int i=M; i<=R; i++) {
        
        right[i-M] = array[i];
    }
    
    
    int i = 0, j = 0, k = L;
    
    //分别从左右两个数组比较数据, 填充到整个数组中
    while (i < LEFT_SIZE && j < RIGHT_SIZE) {

        if (left[i] < right[j]) {
            array[k] = left[i];
            i++;
            k++;
        }else {
            array[k] = right[j];
            j++;
            k++;
        }
    }
    
    //如果右边数组已经循环完毕, 将左边数组的数据依次填充到数组中
    while (i < LEFT_SIZE) {
        array[k] = left[i];
        i++;
        k++;
    }
    //如果做边数组已经循环完毕, 将右边数组的数据依次填充到数组中
    while (j < RIGHT_SIZE) {
        array[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int L, int R) {
    
    if (L == R) {
        return;
    }else{
        int M = (L+R)/2 + 1;
        
        mergeSort(arr, L, M - 1);
        
        mergeSort(arr, M , R);
        
        merge(arr, L, M, R);
        
    }

}

插入排序: 时间复杂度为O(n^2)

/// 插入排序
/// @param array 要排序的数组
void insertionSort(int array[]) {
    
    int i, j, temp;
    
    for (i=1; i < sizeof(&array); i++) {
        
        for (j=i; j > 0 && array[j] < array[j-1]; j--) {
            
            temp = array[j];
            array[j] = array[j-1];
            array[j-1] = temp;
            
        }
    }
}

 快速排序:

空间复杂度为O(logN)

///  快速排序
/// @param array 要排序的数组
/// @param L 数组第0个索引
/// @param R 数组最后一个索引
void quickSort(int array[], int L, int R) {

    //左侧索引大于右侧索引时直接返回
    if (L > R) return;
    
    int i = L, j = R, pivot = array[L], temp;
    
    //双轴左右索引没有相遇之前, 一直循环移动左右索引遍历
    while (L != R) {
        
        //右侧索引在没有找到比pivot小的值之前, 一直向左移动, 一直到找到小于pivot的值后, 停下
        while (array[j] >= pivot && i < j ) {
            j --;
        }
        
        //左侧索引在没有找到比pivot大的值之前, 一直向右移动, 一直到找到大于pivot的值后, 停下
        while (array[i] <= pivot && i < j) {
            i++;
        }
        
        //右侧找到比pivot小的值后, 左侧找到比pivot大的值后, 将数组索引为i和j的值进行交换, 同时在左右没有相遇之前保证i小于j
        if (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

    }
    
    //左右相遇, i就是pivot的位置, 交换L和i的位置
    array[L] = array[i];
    array[i] = pivot;
    
    //找到pivot的位置后, 然后在pivot左右两侧分别进行快排
    quickSort(array, L, i-1);
    quickSort(array, i+1, R);
}

 堆排序: 时间复杂度为O(nlogn)

/// 时间复杂度为O(nlogn )
/// 将父节点值和子节点进行比较, 然后将最大值和父节点值进行交换
/// 堆: 满二叉树 && 父节点的值大于子节点
///  i 节点的父节点:  parent = (i - 1) / 2
///  i 节点的左节点: c1 = 2 * i + 1
///  i 节点的右节点:  c2  = 2 * i +  2
///  要对第i个节点进行heapify, 先找到第i个节点的两个子节点, 然后进行值比较, 交换
/// @param tree 满二叉树(数组表示 , 从上往下, 从左往右)
/// @param n 数组的节点
/// @param i 要对哪个节点进行heapify ( 堆化 )
void heapify(int tree[], int n, int i) {
    if (i >= n) return;
    
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    int max = i;
    
    if (c1 < n && tree[c1] > tree[max]) {
        max = c1;
    }
    
    if (c2 < n && tree[c2] > tree[max]) {
        max = c2;
    }
    
    if (max != i) {
        int temp = tree[max];
        tree[max] = tree[i];
        tree[i] = temp;
    }
    
}


/// 交换数组的两个值
/// @param tree <#tree description#>
/// @param i <#i description#>
/// @param j <#j description#>
void swap(int tree[], int i, int j) {
    int temp = tree[i];
    tree[i] = tree[j];
    tree[j] = temp;
}


/// 构建堆
/// @param tree 表示树的数组
/// @param n 数组的个数
void build_heap(int tree[], int n) {
    int last_node = n - 1;
    int parent = (last_node - 1) / 2;
    int i;
    for (i = parent; i >= 0; i--) {
        heapify(tree, n, i);
    }
}


/// 堆排序
/// @param tree 表示树的数组
/// @param n 数组的个数
void heap_sort(int tree[], int n) {
    build_heap(tree, n);
    int i;
    for (i = n - 1; i > 0; i--) {
        swap(tree, i, 0);
        heapify(tree, i, 0);
    }
    
    
}

整形转字符串的时间复杂为:

相当于N经过多少次除以10等于0, 所以其时间复杂度为logN

/** 数字转字符串*/
func intToString(_ num: Int) -> String {
    
    var temNum = num
    
    var s = ""
    while temNum>0 {
        s += "(temNum%10)"
        temNum /= 10
    }
    
    s.reversed()
    return s
}

下面的算法的时间复杂度为N*logN

第一层for循环,相当于sz从1开始, 经过多少次乘以2等于n, 或者n经过多少次除以2等于1, 所以第一层的时间复杂度为logN

void hello(int n) {
    
    for (int sz = 1; sz < n; sz += sz) {
        
        for (int i = 1; i < n; i++) {
            printf("hello world");
        }
    }
}

递归调用求x的n次方的函数的时间复杂度为logN

double pow(int x, int n) {
    assert( n >= 0);
    
    if (value == 0) return 1;

    double value = pow(x, n/2);
        
    if (n%2) {
         return value*value*x;
    }
    
    return value*value;
}

经过2次递归调用的时间复杂度为:

1 + 2 + 4 + 8 = 15

2^0 + 2^1 + 2^2 + 2^3 + ... + 2^n = 2^n+1 -1

int f(int n) {
    assert(n >= 0);
    if (n == 0) {
        return 1;
    }
    
    return f(n-1) + f(n-1);
}