java时间/空间复杂性

Question

准备考试。我认为时间复杂度是O（n^2），空间复杂度是O（1）。请帮忙，我说得对吗

public static String lastSubstring(String s) {
    
    int start=0;
    int end = start+1;
    int len =0;
    
    while (end + len < s.length()) {

        if (s.charAt(start + len) == s.charAt(end + len)) {
            len++;
        } else if (s.charAt(start + len) > s.charAt(end + len)) {
            end += len + 1;
            len = 0;
        } else {
            start = end;
            end = start + 1;
            len = 0;
        }
    }
    return s.substring(start);
}

Answer 1

时间复杂度为O（n），空间复杂度为O（1），其中n是输入字符串的长度

空间复杂度为O（1），因为除了“start”、“end”、“len”等变量外，没有使用额外的空间。我在这里假设您没有考虑返回字符串占用的空间，如果考虑到这一点，那么空间复杂性将变为O（n），因为最坏情况下，长度为n的完整字符串将返回

时间复杂度为O（n），因为外部变量“end”仅从0增加到n。当“end”大于输入长度n时，while循环中断

时间复杂度应该是O（n^2），如果对于从0到n的每个“end”迭代，您迭代另一个内部变量，比如从0到n的“len”。 但在您的情况下，迭代次数是“end”+“len”的函数，即使您必须从0重新开始“len”，迭代次数也只会增加到n+n=2n。这就是为什么这里的时间复杂性是O（n）