算法

Posted on | In | | Visitors:

算法的概念

一个问题可以有多种算法，每种算法都有不同的效率
算法评定从时间复杂度和空间复杂度计算

时间复杂度和空间复杂度

时间复杂度： 执行算法所需要的计算工作量，一般来说，计算机算法是问题规模N的函数f(n),算法的时间复杂度也因此记作T（n）= O(f(n))

计算方式：

  • 得出算法的计算次数

    1
    2
    3
    4
    5
    #1+2+3+4+...+n
    for(i=1;i<=n; i++){
        $sum += i;
    }
    #总共循环了n次，所以时间复杂度为O(n)

  • 用常数1来取代所有时间中的加法常数

  • 在修改后的运行次数函数中，只保留最高阶
  • 如果最高阶存在且不是1，则去除与这个数相乘的常数

    举例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    function test($n) {
        echo $n;
        echo $n;
        echo $n;
    }
    #计算3次，O(3)--记作->O(1)

    for($i = 1; $i<= $n;$i++) {
        for ($j = 1;$j<=$n;$j++) {
            $sum += $j;
        }
    }

    #n * n 次 时间复杂度为O(n^2)

    for($i = 1; $i<= $n;$i++) {
        for ($j = 1;$j<=$n;$j++) {
            $sum += $j;
        }
    }
    for () {
        n次
    }
    echo $a + b 
    #n^2 + n + 1 --->忽略 --> O(n^2)

    while($n>=1) {
        $n = $n/2;
    }
    #n执行次数

    n/(2^m) = 1
    #m = log2n,所以时间复杂度O(log2n)

效率排名：O(1)>O(log2n)>O(n)>O(nlog2n)>O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)

最坏的情况：最坏情况时的运行时间，一种保证，如果没有特别说明，说明时间复杂度为最坏的时间复杂度

空间复杂度

S(n) = O(f(n)),算法需要消耗的内存空间

包括程序代码、输入数据、辅助变量所占用的空间

计算方式：

有时用空间换取时间
冒泡排序的元素交换，空间复杂度就是O(1)

常见排序算法

冒泡排序、直接排序、希尔、选择、快速、堆、归并排序

  • 冒泡排序

    原理：两两相邻的数进行比较，如果反序就交换，否则不交换

时间复杂度：最坏O(n^2),空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#m冒泡排序
1,3,2,4,6,5
1,3,2,4,6,5
1,2,3,4,6,5
1,2,3,4,6,5
1,2,3,4,5,6

for ($i=0;$c = count($arr);$i<$c;$i++){
    for($j=0;$j<$c;$j++) {
        $arr[$j] = $arr[$j+1];
        $temp = $arr[$j];
        if ($arr[$j] > $arr[$j+1]) {
          $arr[$j+1] = $temp;
        }
    }
}
  • 直接插入排序

    原理：每次从无序表中取出一个元素，把它插入到有序表的合适的位置，使有序表依然有序

时间复杂度O(n^2),空间复杂度O(1)

  • 希尔排序

    把待排序的数据很具增量分成几个子序列，对子序列进行插入排序，直到增量为1，直接进行插入排序；增量的排序一般是数组长度的一半，再变为原来增量的一般，知道增量为1

时间复杂度O(n^2)空间复杂度O(1)

  • 选择排序

    每次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

时间复杂度 O(n^2),空间复杂度O(1)

  • 快速排序

    通过一趟排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按照此方法对这两个部分数据进行快速排序，整个排序过程可以递归完成

时间复杂度为最差O(n^2)平均O(nlog2n)
空间复杂度为O(n)，平均O(nlog2n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

  • 堆排序

    把待排序的元素按照大小在二叉树位置上排序，排序好的元素要满足：父节点的元素要大于等于子节点；这个过程叫做堆化过程，如果根节点存放的是最大的数，则叫做大跟堆，如果是最小，就叫小根堆，可以把节点拿出来，然后再堆化，循环到最后一个节点

时间复杂度：O(nlog2n)
空间复杂度：O(1)

  • 归并排序

    将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列

时间复杂度O(nlog2n)
空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//交换函数
function swap(array $arr,$a,$b) {
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b = $temp];
}
//归并算法总函数
function mergeSort(array $arr) {
    $start = 0;
    $end = count($arr) - 1;
    Msort($arr,$start,$end);
}
functin Msort(array &$arr,$start,$end) {
    //当子序列长度为1时，$start == $end,不再分组
    if ($start < $end) {
        $mid = floor(($start + $end) / 2);//将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
        MSort($arr,$start,$mid);//将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
        MSort($arr,$mid + 1,$end);//将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
        Merge($arr,$start,$mid,$end); //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
    
    }
}
//归并操作
function Merge(array &$arr,$start,$mid,$end){
    $i = $start;
    $j=$mid + 1;
    $k = $start;
    $temparr = array();

    while($i!=$mid+1 && $j!=$end+1)
    {
       if($arr[$i] >= $arr[$j]){
           $temparr[$k++] = $arr[$j++];
       }
       else{
           $temparr[$k++] = $arr[$i++];
       }
    }

    //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($i != $mid+1){
        $temparr[$k++] = $arr[$i++];
    }
    //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($j != $end+1){
        $temparr[$k++] = $arr[$j++];
    }
    for($i=$start; $i<=$end; $i++){
        $arr[$i] = $temparr[$i];
    }
}

常见查找算法

  • 二分查找

    从数组的中间元素开始，如果中间元素正好是要查找的元素，搜索结束，如果某一个特定元素大于或者小于中间元素，则在数组大于或者小于中间元素的一半中查找

时间复杂度最差O（log2n）空间复杂度迭代o(1),递归O（nlog2n）

  • 顺序查找

    按一定的顺序检查数组中的每一个元素，直到找到所要寻找的特定值为止

时间复杂度：O(n) 空间复杂度O(1)

其他算法

1,1,2,3,5,8,13,21,34…第30位是多少？使用伪代码描述其实现方法。 伪代码就是文字描述就可以

1
2
3
4
5
$arr = [1,1];
for ($i=2;$i<30;$i++) {
    $arr[$i] = $arr[$i-1] + $arr[$i-2];
}
var_dump($arr);