问题描述

有两个数组 A 和 B 。并且 A 数组 = B 数组，现将 B 数组中的其中一个值随机去掉，求被去掉的值。

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?php
$arr1 = array(1,2,3,4,5);
$arr2 = array(1,2,3,5);

for($i=0; $i<count($arr1); $i++){
	$flag = false;
	for($j=0; $j<count($arr2); $j++){
		if($arr1[$i] == $arr2[$j]) {
			$flag = true;
			break;
		}
	}
	if(!$flag)
		echo $arr1[$i];
}

算法时间复杂度

信息标记

1
2
3
4
5
6
7
8
9
10
11
for($i=0; $i<count($arr1); $i++){//{1}
	$flag = false; //{2}
	for($j=0; $j<count($arr2); $j++){ //{3}
		if($arr1[$i] == $arr2[$j]) {
			$flag = true;
			break;
		}
	}
	if(!$flag) //{6}
		echo $arr1[$i]; //{7}
}

计算过程

第一步：计算算法运行过程中运行的代码总的条数N:

1
N = n*n + n + n +1

n 代表{1}循环n次

{3} 过程中每条执行1次，所以得到 n*n

{2} 过程中 $flag = false 被赋值 n次，所以 +n

{6} 过程中 if(!$flag) 判断了 n 次，所以 +n

{7} 最后输出，所以 +1

第二步：计算算法总运行时间f(n):

1
f(n) = N * t = (n^2 + 2n +1) * t

第三步：计算时间复杂度T(n):

1
2
3
T(n) = O( f(n) ) = O( (n^2 + 2n +1) * t )
即
T(n) = O( (n^2 + 2n +1) * t )

第四步：简化

1
T(n) = O(n^2)