全局变量是否需要更长的获取时间？

Question

下面的代码适用于附加输入。

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreakMemo(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
    }

    private boolean wordBreakMemo(String s, Set<String> wordDict, int start, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && wordBreakMemo(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

但是当我如下将局部变量更改为全局变量时，我的代码需要更长的时间来执行，导致 LeetCode 上的 'Time Limit Exceeded'。

class Solution {
    HashSet<String> set;
    String s;
    Boolean dp[];
    public boolean wordBreak(String s, List<String> wordDict) {
        
        set=new HashSet();
        set.addAll(wordDict);
        this.s=s;
        dp=new Boolean[s.length()];
        return wordMemo(0);
    }
    public boolean wordMemo(int start)
    {
        if(start==s.length())
            return true;
        
        if(dp[start]!=null)
            return dp[start];
        
        for(int i=start+1; i<=s.length(); i++)
        {
            if(set.contains(s.substring(start, i)) && wordMemo(i))
            {
                dp[start]=true;
                return true;
            }
        }
        return false;
    }
}

输入：

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

有人可以解释一下这里发生了什么吗？

Answer 1

全局变量的获取时间并不慢，不。

每当您在编码挑战中遇到超出时间限制的情况时，您应该假设您的算法或数据结构存在缺陷或错误。它绝不是微观因素，例如获取时间或访问修饰符或您选择的语言。即使您可以通过更好的内存访问模式将程序速度提高 10%，或者通过从 Python 切换到 C 来提高 100%，您也可能会降低 10,000% 或 10,000,000%，而不是 100%。这就是当你的程序意外地 O(n²) 或 O(2ⁿ) 而挑战设计者期望 O(n ).

这里，第一个程序有：

return memo[start] = false;

而第二个刚刚：

return false;

它从不记忆 false 结果。有更多的重复计算，足以杀死算法的 Big-O 时间复杂度。

全局变量是否需要更长的获取时间？

Do global variables take longer fetch time?

java

algorithm

dynamic-programming