PHP面试之四：逻辑与算法

数据结构

• 常见数据结构

Array 数组是 最简单 而且 应用最广泛 的数据结构

特征：
1、使用连续内存空间来存储
2、存放相同类型或着衍生类型的元素（PHP数组比较特别，可以存放八种数据类型）
3、通过下标来访问

Set 集合

特征：
1、保存不重复的元素

Map 字典

特征：
1、就是PHP关联数组，以Key/Value形式存储

Stack 栈，与队列相似

特征：
1、存储数据是先进先出，栈只有一个出口，只能从栈顶部添加和删除元素

Heap 堆，与二叉树的数据结构相似

特性：
1、子节点的键值和索引总小于他的父节点

list 线性表，由零个或多个数据元素组成的有序序列

特性：
1、线性表是一个序列，在PHP中就是索引数组

Queue 队列

特性：
1、先进先出，并发中使用，可以安全地将对象从一个任务传给另一个任务，可以使用PHP数组模拟

• 如何模拟双向链表？

使用数组Array来实现
array_shift() / array_unshift()
array_pop() / array_push()

其它逻辑算法

• 重点：找出算法的规律，再用代码来实现

模拟PHP内置函数来实现某些功能

不使用PHP内置函数的前提下，实现字符串翻转

function str_rev($str){

    for($i=0;true;$i++){
        if(!isset($str[$i])){
            break;
        }
    }
    $return = '';
    for($j=$i-1;$j>=0;$j--){
        $return .= $str[$j];
    }
    return $return;
}

常见算法考点

• 算法是什么？

是一种解决问题的计算方法，一个问题有多种算法来解决，每种算法效率都不同，根据需求选择最优算法

• 时间复杂度和空间复杂度

作用：用于 评定 某算法 是否合适？是否高效？

时间复杂度：执行算法所需要的时间
空间复杂度：执行算法所需要的内存空间

常见时间复杂度 例如：常数阶O(1)、线性阶O(n)、平方阶O(n^2)、立方阶O(n^3)、对数阶O(log2n)、nlog2n阶O(nlog2n)、指数阶O(n^n)

效率从大到小：O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)

时间复杂度计算方式：得出算法的计算次数（空间复杂度与之类似）
用1来取代说有确定次数的加法

• 常见排序算法

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

冒泡排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(n^2)
空间复杂度      O(1)

直接插入排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(n^2)
空间复杂度      O(1)

希尔排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(nlog2n)
空间复杂度      O(1)

选择排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(n^2)
空间复杂度      O(1)

快速排序
               最坏情况        平均情况
时间复杂度      O(n^2)         O(nlog2n)
空间复杂度      O(n)           O(log2n)

归并排序
               最坏情况        平均情况
时间复杂度      O(nlog2n)         O(nlog2n)
空间复杂度      O(n)

堆排序
               最坏情况        平均情况
时间复杂度      O(nlog2n)      O(nlog2n)
空间复杂度      O(1)

• 常见查找算法

二分查找、顺序查找

二分查找        最坏情况        平均情况
时间复杂度      O(log2n)       O(log2n)
空间复杂度      迭代O(1)       递归O(log2n)

顺序查找        最坏情况        平均情况
时间复杂度      O(n)           O(n)
空间复杂度      O(1)