我已经用PHP编程很长时间了，因为我不是来自计算机科学/数学背景，所以我对Big O符号只有基本的了解，所以我取了一个函数，并试图改进它，并用大0表示它们:
function foo($j) {
$ids = array();
while (count($ids) < $j) {
$id = gen_id(); // assume this function will return you an integer
if (!in_array($id, $ids)) {
$ids[] = $id;
}
}
return $ids;
}
我将通过删除count($ids)的while循环并替换为for循环来改进此功能，以便count($ids)不必每次在循环中进行评估，并且还将is_array替换为isset并将值移动到键(isse t比in_array更快)
示例2 -改进
function foo($j) {
$ids = array();
for($i = 1; $i<= $j; ++$j) {
$id = gen_id(); // assume this function will return you an integer
if (!isset($ids[$id])) {
$ids[$id] = true;
}
else {
--$i;
}
}
return $ids;
}
我将用以下大0符号表示上述函数:
示例1: O (n ^ 2), 示例2: O (n)
我的记号正确吗?还有更好的方法来做同样的函数吗?
提前感谢!
我将以更直接的方式编写该函数:内部for循环是do ... while循环的完美场景。
function foo( $j)
{
$ids = array();
for( $i = 0; $i < $j; $i++)
{
do
{
$id = gen_id();
} while( isset( $ids[$id]));
$ids[$id] = true;
}
return $ids;
}
Edit:实际上，这个函数是O($j)/O(n)，因为gen_id()和isset()都是常量O(1) (isset()是一个哈希表查找)。因此，for循环的内部效率为常数时间O(1)，使得整个函数为O(n)。
首先:常数系数在大0符号中不重要，这意味着O(n) = O(cn)对应任何常数c != 0。
对于第一个，我知道count($ids)需要O(1)的时间来计算，那么in_array($id, $ids)呢?我不太清楚。但如果是O(n)或O(logn)，那么整个就是O(n^2)或O(nlogn)。我不认为这可以在O(1)时间内实现，这可能会给整个功能一个O(n)时间。
对于第二个，这是O(n)，似乎比第一个快。
EDIT:我只是觉得维基百科在某种程度上清楚地描述了大0符号。
你的想法很好，但你不正确。
下面将澄清您....
function foo($j)
{
for($i=1;$i<j;$i++)
{
// some code here
}
for($i=1;$i<j;$i++)
{
// some code here
}
}
你可能认为这将是0(2n)，但常数项并不以0符号表示。所以复杂度为0(n)
看下面的
function foo($j)
{
for($i=1;$i<j;$i++)
{
for($k=1;$k<i;$k++)
{
// some code here
}
}
}
复杂度为0(n^2)
for ($i=0;$i<$j; ) {
$id = gen_id();
if (!isset($ids[$id])) {
$ids[$id]=true;
$i++;
}
}