php中时间复杂度取决于算法实现而非语言本身；需识别代码结构、明确输入规模n、分析主导操作次数，并区分最好/最坏/平均情况。
PHP 中的时间复杂度不是语言特性，而是算法在 PHP 中实现时的性能表现。面试中考察的其实是你能否识别代码背后的算法结构，并准确估算其执行时间随输入规模增长的趋势。
常见 PHP 操作对应的时间复杂度
理解内置函数和数据结构的操作成本，是分析时间复杂度的基础：
- 数组（索引数组）访问 $arr[$i]：O(1)，底层是 C 的连续内存，直接计算偏移量
- 数组末尾追加 $arr[] = $x 或 array_push()：均摊 O(1)，PHP 数组是动态哈希表，扩容有代价但不频繁
- 数组头部插入 array_unshift() 或按值查找 in_array()：O(n)，需整体移动或遍历
- 关联数组键查找 $arr['key']：O(1) 均摊，基于哈希表；最坏情况（大量哈希冲突）为 O(n)，但实际极少发生
- sort()、usort() 等排序函数：O(n log n)，PHP 7+ 使用双轴快排 + 插入排序混合策略
- array_unique()、array_merge()、array_flip()：基本为 O(n)，依赖单次遍历与哈希映射
嵌套循环与递归的复杂度判断要点
面试题常以简单循环或递归形式出现，关键看迭代次数是否与输入规模 n 直接相关：
- 两层独立 for 循环（非嵌套），如先遍历一次数组再遍历一次：O(n + m) → 视为主 O(n)
- 外层 i 从 0 到 n−1，内层 j 从 i+1 到 n−1（典型两两比较）：执行约 n²/2 次 → O(n²)
- 每次将问题规模减半的递归（如二分查找模拟）：递归深度 log₂n，每层 O(1) → O(log n)
- 斐波那契朴素递归（未记忆化）：子问题重复计算，递归树节点数呈指数级 → O(2ⁿ)
PHP 特定陷阱：隐式循环与自动类型转换
有些写法看似简洁，实则暗含高开销操作，容易在面试中被追问：
立即学习“PHP免费学习笔记（深入）”；
- 用 == 比较两个大数组：PHP 会逐元素对比，等价于 O(n)，且涉及类型转换逻辑，比 === 慢得多
- foreach 遍历超大对象或生成器不当使用：若在 foreach 内部反复调用 count() 或 sizeof()（尤其对未缓存长度的 SPL 对象），可能触发重复计算
- 正则匹配 preg_match() 处理超长字符串 + 复杂模式：最坏可达 O(n²) 或指数级（回溯灾难），需提醒避免用户可控输入触发恶意模式
- 引用传递缺失导致数组被复制：如函数参数没加 &，传大数组会触发写时复制（Copy-on-Write），虽不改变时间复杂度阶数，但显著增加常数时间，影响实际性能
如何在面试中清晰表达复杂度分析
不要只报一个“O(n²)”，要体现思考过程：
- 明确说明 n 是什么（例如：“n 是输入数组的长度”）
- 指出主导项来源（例如：“外层循环执行 n 次，内层平均执行 n/2 次，乘积主导时间增长”）
- 区分最好/最坏/平均情况（如快速排序：最坏 O(n²)，平均 O(n log n)）
- 如果做了优化（如哈希表预存、双指针、记忆化），说明优化前后变化及依据
