Schlechte Laufzeit von O (n^2) Algorithmus

Question

Ich versuche SPOJ Beads mit Haskell zu lösen, aber ich überschreite das Zeitlimit. Ich bin ziemlich sicher mein Algorithmus Komplexität ist das Beste, was ich bekommen kann. Deshalb bin ich misstrauisch, dass Haskell selbst das Problem ist (Bibliothek, Strenge usw.), aber ich habe keine Ahnung, was es sein könnte.

import   Data.Array 
import   Data.List 

main :: IO() 
main = do 
    x <- readLn 
    interact $ unlines . fmap proccess . take x . lines 

proccess :: String -> String 
proccess line = show $ minimumDisjoint line 

minimumDisjoint :: String -> Int 
minimumDisjoint s = minimumBy sortFn [1..len] -- gets minimum elem from list O(n) 
    where 
    len = length s 
    str = listArray (1, len) s 
    sortFn i1 i2 = foo i1 i2 -- basically 'string1 > string2' O(n) 
     where 
     foo i3 i4 
      | i3 > len  = foo 1 i4 
      | i4 > len  = foo i3 1 
      | i3 == i1 -1 = ord 
      | ord == EQ  = foo (i3+1) (i4+1) 
      | otherwise  = ord 
      where 
      ord = compare (str ! i3) (str ! i4) 

Vielen Dank für jeden Hinweis!

Answer 1

Ihr schlimmster Fall ist Zeichenfolge mit allen Elementen gleich, sieht aus wie minimumDisjoin ist O (n^2).

Vielleicht würde dies umgehen, und kann O (n) sein:

Ein Pass über Zeichenfolge finden Liste des Indizes des minimalen Elements.

Aber anstatt eine Liste, die Sie Position und Länge wollen aufeinanderfolgender Läufe von Indizes starten: Lauflänge codiert

Handhabung Wrap geht um nächste.

Dann Position (en) nach dem längsten Lauf (s) nehmen.

Der nächste Durchgang muss nur Punkte nach dem längsten Lauf vergleichen. Im schlimmsten Fall ist dies die halbe Größe der ursprünglichen Liste und vergleicht nichtüberlappende Strings, viel effizienter als das ursprüngliche überlappende Problem.