为什么这个O(n ^ 2)代码比O(n)执行得更快？

Question

我编写了两种方法的代码,以找出LeetCode上字符串中的第一个唯一字符.

问题陈述: 给定一个字符串,找到其中的第一个非重复字符并返回它的索引.如果它不存在,则返回-1.

样本测试案例:

s ="leetcode"返回0.

s ="loveleetcode",返回2.

方法1(O(n))(如果我错了,请纠正我):

class Solution {
    public int firstUniqChar(String s) {

        HashMap<Character,Integer> charHash = new HashMap<>();

        int res = -1;

        for (int i = 0; i < s.length(); i++) {

            Integer count = charHash.get(s.charAt(i));

            if (count == null){
                charHash.put(s.charAt(i),1);
            }
            else {
                charHash.put(s.charAt(i),count + 1);
            }
        }

        for (int i = 0; i < s.length(); i++) {

            if (charHash.get(s.charAt(i)) == 1) {
                res = i;
                break;
            }
        }

        return res;
    }
}

方法2(O(n ^ 2)):

class Solution {
    public int firstUniqChar(String s) {

        char[] a = s.toCharArray();
        int res = -1;

        for(int i=0; i<a.length;i++){
            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {
                res = i;
                break;
            }
        }
        return res;
    }
}

在方法2中,我认为复杂性应该是O(n ^ 2),因为indexOf在这里以O(n*1)执行.

但是当我在LeetCode上执行两个解决方案时,我的方法2的运行时间为19毫秒,方法1的运行时间为92毫秒.为什么会这样？

我想LeetCode测试最佳,最差和平均情况下的小输入值和大输入值.

更新:

我知道O(n ^ 2算法)对于某些n <n1可以表现得更好.在这个问题中,我想了解为什么在这种情况下会发生这种情况.即方法1的哪一部分使其变慢.

LeetCode链接到问题

Answer 1

考虑:

• f ₁(n)= n ²
• f ₂(n)= n + 1000

显然,f ₁是O(n ²),f ₂是O(n).对于小输入(例如,n = 5),我们有f ₁(n)= 25但f ₂(n)> 1000.

仅仅因为一个函数(或时间复杂度)是O(n)而另一个函数是O(n ²)并不意味着前者对于n的所有值都更小,只是有一些n超出了它将是这种情况.

Answer 2

对于非常短字符串,例如单个角色作成的成本HashMap,重新调整其大小,查找条目而装箱和拆箱char到Character可能掩盖的成本String.indexOf(),这可能是考虑热内联由JVM两种方式.

另一个原因可能是RAM访问的成本.随着更多的HashMap,Character并Integer参与查找的东西都有可能被需要,并从RAM额外的访问.单次访问大约100 ns,这可以加起来.

看看Bjarne Stroustrup:为什么你应该避免链接列表.本讲座说明了性能与复杂性不同,内存访问可能是算法的杀手.

Answer 3

Big O表示法是对算法在内存消耗或计算时间方面进行扩展的方式的理论度量N- 元素或主导操作的数量,并始终为N->Infinity.

在实践中,N在你的例子中相当小.虽然向散列表添加元素通常被认为是分摊的O(1),但它也可能导致内存分配(同样,取决于散列表的设计).这可能不是O(1) - 并且还可能导致进程对内核进行系统调用以获取另一个页面.

采取O(n^2)解决方案 - 字符串in a将很快发现自己在缓存中,并可能不间断地运行.单个内存分配的成本可能高于嵌套循环对.

在使用现代CPU架构的实践中,N在使用理论上最优的算法优于线性数据结构和线性搜索之前,读取形式高速缓存比来自主存储器的读取快几个数量级 .二叉树对于缓存效率来说是特别坏的消息.

[编辑]它是Java:哈希表包含对盒装java.lang.Character对象的引用.每次添加都会导致内存分配

Answer 4

O(n ²)只是第二种方法的最坏情况时间复杂度.

字符串,例如bbbbbb...bbbbbbbbbaaaaaaaaaaa...aaaaaaaaaaa其中存在xb以及x一个的,每次循环迭代约需x步骤来确定索引,因此总执行的步骤为约.对于大约30000,大约需要1~2秒,而另一个解决方案将表现得更好.2x2x

在线尝试,该基准计算出方法2比上述字符串的方法1慢约50倍.对于更大的x,差异甚至更大(方法1需要大约0.01秒,方法2需要几秒钟)

然而:

对于从{a,b,c,...,z} ^[1]中统一选择每个字符的字符串,预期时间复杂度应为O(n).

这是正确的,假设Java使用天真的字符串搜索算法,该算法逐个搜索字符直到找到匹配,然后立即返回.搜索的时间复杂度是所考虑的字符数.

它可以很容易地证明(证明类似于这个Math.SE帖子 - 直到第一个头的翻转次数的预期值)特定字符在字母表上的统一独立字符串中的预期位置{a,b,c,...,z}是O(1) .因此,每个indexOf和lastIndexOf调用在预期的O(1)时间内运行,整个算法需要预期的O(n)时间.

^[1]:在最初的leetcode挑战中,据说是

您可以假设该字符串仅包含小写字母.

但是,问题中没有提到这一点.