YOU'VE MADE A BRAVE DECISION, WELCOME.

每一个不曾起舞的日子都是对生命的辜负。

| 算法 时间复杂度

数据结构（学习累积中）

iOS常见的算法（学习中）

  • 冒泡算法
  • 选择排序
    • 先从未排序的的序列中找到最小（大）值，存放到排序的起始位置
    • 再从剩余未排序的元素中寻找最大（小）值，存放到已排序的末尾
    • 循环，直到结束。
  • 快速排序
    • 以第一个数为基数
    • 从右边开始，比基数大放右边，比基数小放左边
    • 接着从左边开始，比基数大放右边比基数小放左边
    • 再判断比较最左边和最右边两个数变化后的位置
    • 始终保持小的在左边大的在右边
    • 递归
  • 归并排序
  • 二分法查找排序
  • 二叉树遍历

时间复杂度

  • 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    x=91; y=100;
    while(y>0) {
    	if(x>100) {
    		x=x-10;
    		y--;
    	} else 
    	x++;
    }
    T(n) = O(1)

  • 当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的

    1
    2
    3
    4
    5
    6
    7
    x=1; 
    for(i=1;i<=n;i++) 
    	for(j=1;j<=i;j++)
        	for(k=1;k<=j;k++)
            	x++; 
            	
    T(n) = O(n3)

  • 算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

    1
    2
    3
    4
    5
    6
    7
    A[0...n-1]查找给定k值得算法
    i=n-1;            
    while(i>=0&&(A[i]!=k))       
          i--;        
    return i;
    如果

  • O(1): 表示算法的运行时间为常量

  • O(n): 表示该算法是线性算法
  • O(㏒2n): 二分查找算法
  • O(n2): 对数组进行排序的各种简单算法，例如直接插入排序的算法。
  • O(n3): 做两个n阶矩阵的乘法运算
  • O(2n): 求具有n个元素集合的所有子集的算法
  • O(n!): 求具有N个元素的全排列的算法
  • 优<—————————<劣
    • O(1)<O(㏒2n)<O(n)<O(n2)<O(2n)