时间戳

首页 > 解决方案 > O(sumof(n)) 时间复杂度

algorithm - O(sumof(n)) 时间复杂度

问题描述

问题很简单直接：是否存在时间复杂度 O(总和(n))

这是写它的正确方法吗？我问是因为我写的这个程序：

    def check(self, front, s, back):
        if(s[front:back] == s[front:back][::-1]): 
            return s[front:back]
        else: 
            return self.check(front, s, back-1)

    def checkIter(self, front, s, back, longest):
        r = self.check(front, s, back)
        if(len(r) >= len(longest)): longest = r
        if(front < back):
            return self.checkIter(front+1,s,back, longest)
        else:
            return longest
        
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        return self.checkIter(0,s,len(s),"")

它的输入longestPalindrome('cbbd')运行约 10 次产生输出：

"cbbd" "cbb" "cb" "c" "bbd" "bb" "b" "bd" "b" "d". 在给定的相同输入上longestPalindrome('cbbda')： "cbbda" "cbbd" "cbb" "cb" "c" "bbda" "bbd" "bb" "b" "bda" "bd" "b" "da" "d" "a"所以这不可能是 O(n)

标签： algorithmtime-complexitybig-ocomplexity-theory

解决方案

指定的总和等于n(n+1)/2。因此，它在O(n^2).

推荐阅读