1

我有三个函数：_sort、_strpos、_array_int

<?php
class timer{
    private $_start;
    private $_end;
    public function program_begin(){
        $this->_start = microtime(true);
    }
    public function program_end(){
        $this->_end = microtime(true);
    }
    public function get_time(){
        $time_use = ($this->_end - $this->_start)*1000;
        echo $time_use."ms\n";
    }
};
$t = new timer();
$test_cnt = $argv[1];
$s_len1 = $s_len2 = $argv[2];
$t->program_begin();
for($j = 0; $j<$test_cnt; $j++){
    for($i = 0; $i < $s_len1; $i++)
        $s1 .= chr(rand()%26+97);

    for($i = 0; $i < $s_len2; $i++)
        $s2 .= chr(rand()%26+97);

    $flag = call_user_func($argv[3],$s1, $s2);
    $s1=$s2="";
}
$t->program_end();
$t->get_time();

function _sort($s1, $s2){
    for($i = 0; $i < strlen($s1); $i++)
        $arr[] = $s1[$i];

    sort($arr);

    for($i = 0; $i < strlen($s2); $i++)
        if(!search_part($arr, $s2[$i]))
            return false;

    return true;

}
function search_part($arr, $key){
    $s = 0; 
    $e = count($arr)-1;
    while($s<=$e){
        $m = (int)(($s+$e)/2);
        if($arr[$m] > $key)
            $e = $m-1;

        if($arr[$m] < $key)
            $s = $m+1;

        if($arr[$m] == $key)
            return true;
    }
    return false;
}

function _strpos($s1, $s2){
    for($i = 0; $i < strlen($s2); $i++)
        if(strpos($s1,$s2[$i]) === false)
            return false;

    return true;
}

function _array($s1, $s2){
    for($i = 0; $i < strlen($s1); $i++)
        $arr[$s1[$i]] = 1;

    for($i = 0; $i < strlen($s2); $i++)
        if(!isset($arr[$s2[$i]]))
            return false;

    return true;
}

function _array_int($s1,$s2){
    for($i = 0; $i < strlen($s1); $i++)
        $arr[ord($s1[$i])] = 1;

    for($i = 0; $i < strlen($s2); $i++)
        if(!isset($arr[ord($s2[$i])]))
            return false;

    return true;
}

我认为时间复杂度：
_sort(as func A) : O(nlgn)
_array_int(as func B): O(n)
_strpos(as func C): O(n^2)

因此速度似乎是B>A> C

但测试结果是：C>B>A
我无法解释为什么 C 最快。

像这样测试它php test.php test_count word_lenght test_func

4

2 回答 2

0

您的 O(n^2) 可能比其他人执行得更快的原因之一是它包含一个错误。

if(!strpos($s1,$s2[$i]))
        return false;

这实际上意味着“如果没有字符或它是 $s1 中的第$s2[$i]一个字符，则返回 false。”，因为字符串索引从 0 开始。这可能不是您想要的，因为它会在两个字符串开始时立即返回例如，具有相同的字符。（您可以通过使用来解决此问题）$s1 falseO(1) if(strpos($s1,$s2[$i]) === false)

其次，您用于测试的输入对于您获得的结果至关重要。由于O(10*n)is still O(n)，因此不能保证对于小输入，O(n)算法将比 a 执行得更快O(n²)，依此类推。n当变得足够大时，此保证是渐近结果。此外，算法的特殊性也可能导致特定情况下的不同性能，而不是“最坏情况”。例如，如果其中一个字符串明显小于另一个，或者($s2, $s1)满足其他特殊条件，特别是因为您允许您的算法快速返回false尽快，不必一直处理两个字符串。

最后，您的O(n)算法通常应该在这 3 个中表现最好，尤其是随着输入大小的增加，但不一定保证它在每个输入上都会表现得更好。

于 2013-06-24T05:13:08.530 回答
-1

如果您只是使用str_split匹配一个字符串是否是另一个字符串的一部分。您的代码似乎不必要地复杂。

  $string1 = "ABCD";
  $string2 = "AABCDEF";

  $origin = str_split($string1);
  $other = str_split($string2);

  foreach ($origin as $char) {
      if (in_array($char, $other)) {
          //char found
      } else {
          //char not found
      }
  }
于 2013-06-24T04:50:06.547 回答