O（n）???谁能告诉我的.reverse

-2

大O说，我用下面的方法来搜索回文。我知道第一个是O（n），因为它贯穿整个字符串。 StringBuffer中的.reverse（）是否也执行O（n）？我不担心找到一个更好的方法来解决问题我试图了解是否反向方法在物理上颠倒了字符串，还是比它更有效率？感谢O（n）???谁能告诉我的.reverse

public static boolean isAPalindrome(String s1){ 

    String tmp = "";  
    int length = s1.length(); 
    for(int i = 0; i < s1.length(); i++){   
     tmp += s1.charAt(s1.length()-i-1); 
    }  
    if (s1.equals(tmp)) return true; 
    return false;   

} 

public static boolean isAPalindrome(String s1){ 

    StringBuffer a = new StringBuffer(s1); 
    return s1.equals(a.reverse().toString()); 

}

来源

2016-01-20 Matthew Leighty

http://stackoverflow.com/questions/2439141/what-is-the-most-efficient-algorithm-for-reversing-a-string-in-java – novice

嗨马修，如果一个答案解决了你的问题，请接受通过点击旁边的绿色复选标记。谢谢 – Idos

冲销字符串不能快于O(n)（下字符串的正常表示）。
你必须对字符串的每个字符“操作”，因此它不能理论上比这更快。

StringBuffer延伸AbstractStringBuilder其实施reverse。你可以自己看看源代码here。

注：这是不说StringBuilder/Buffer小号reverse运行快为你写一个O(n)reverse方法。它可能会运行更快。但渐近它仍然是O(n)。

来源

2016-01-20 19:02:45 Idos

这一点，如果你扭转必须检查溶液或东西它只是相同的，没有更好的问题。只是一种不具有继承优势的解决方案。 – jgr208

这根本不对。您可以很好地为具有恒定时间反向操作的字符串建立数据结构。 –

@EmilVikström关心详细说明？ OP显然没有询问Strings的任何模糊表示。任何“正常”的人至少需要O（n）。 – Idos

您可以实现反向，有效地是O（1），但不与典型的字符串类：你可以通过实现一个字符串类与方向构件做，可以采取的值“向前”或“向后”。但是，如果恢复在所有其他计算中占据主导地位，那么这样做才有意义。

来源

2016-01-20 19:21:14

O（n）???谁能告诉我的.reverse

回答

相关问题