下面两个解的Big O运行时间是多少

Question

我想出了以下面试问题的 2 个解决方案

Given 2 different lists of integers, write a function that will return their intersection.

解决方案一： 使用下面的代码，我对两个列表进行排序，然后使用 2 个计数器（每个列表一个）遍历它们。增加指向较小值的指针。如果两个指针指向相同的值，则将其插入结果并递增两个指针。（Returns 个排序的交叉点）

<?php

    function find_intersection($a1, $a2) {

        $intersection = array();
        sort($a1);
        sort($a2);

        $i = $j = 0;
        while($i < count($a1) && $j < count($a2)) {
            if($a1[$i] > $a2[$j]) {
                $j++;
            } else if($a1[$i] < $a2[$j]) {
                $i++;
            } else {
                $intersection[] = $a1[$i];
                $i++;
                $j++;
            }
        }
        return $intersection;
    }
?>

方案二： 这里我迭代第一个列表，将值放入数组，使用值作为键，计数作为值（如果它已经在列表中递增计数 1，否则插入计数 1）。然后迭代list2，如果值在 hashtable and > 0 将该值插入结果数组，递减散列 table.

中的值

下面的解决方案 2 将 return 未排序的交集

function find_intersection2($a1, $a2) {
        $hash_arr = array();
        $intersection = array();
        for($i = 0; $i < count($a1); $i++) {
            if(isset($hash_arr[$a1[$i]])) {
                $hash_arr[$a1[$i]]++;
            } else {
                $hash_arr[$a1[$i]] = 1;
            }
        }

        for($j = 0; $j < count($a2); $j++) {
            if(isset($hash_arr[$a2[$j]])) {
                $intersection[] = $a2[$j];
                $hash_arr[$a2[$j]]--;
            }
        }

        return $intersection;
    }

问题 1) 解决方案#1 的运行时间是多少？由于排序，它是 O(n log n) 吗？你会如何分析它？请解释一下。

问题 2) 对于解决方案 #1，如果我确定我将收到的数组将被排序并且不需要对它们进行排序，那么由于 while 循环迭代，解决方案是否为 O(n)？

问题 3) 对于解决方案 2，它是大 O(n) 因为我是运行 2 个单独的循环吗？

Answer 1

问题 1

解决方案二中有

Sort
Sort
Single loop

循环的复杂度是O(n)，所以要看排序。 According to PHP，它使用Quicksort，所以复杂度是O(n log n)

Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

因此，我们有 O(n log n) + O(n log n) + O(n)。我们取较大的 O(n log n).

问题 2

在那种情况下，您可以删除 sort 调用，这将是 O(n)。如果保留它们，它将继续为 O(n log n)。

问题 3

是的，复杂度是O(n) + O(n)，所以最终的复杂度就是你说的O(n)。

下面两个解的Big O运行时间是多少

What's the Big O run time of the two following solutions

php

big-o

问题 1

问题 2

问题 3