Laufzeit eines Substring-Algorithmus bestimmen

Java-Forum Java-Grundlagen
1

Der String s hat n Zeichen und kann beliebig wachsen.

Wie ist die Zeitkomplexität dieser Substring-Methode? O(n^2), O(n^3) oder etwas ganz anderes?

Vielen Dank

import java.util.Comparator;
import java.util.TreeSet;

public class Algorithm {
    record Elem(int from, int to) {
    }

    public char substringsAlgorithm(final String s, final int m) {
        TreeSet<Elem> set = new TreeSet<>(Comparator.comparing(e -> s.substring(e.from(), e.to())));
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                set.add(new Elem(i, j));
            }
        }

        int m1 = m;
        for (Elem e : set) {
            int len = e.to() - e.from();
            if (m1 < len) {
                return s.substring(e.from(), e.to())
                        .charAt(m1);
            }
            m1 -= len;
        }

        throw new IllegalArgumentException();
    }

    public static void main(String[] args) {
        System.out.println(
            new Algorithm().substringsAlgorithm("dbac", 2) // -> c
        );
    }
}
6

Mhmh, dieser Algorithmus berechnet alle möglichen Substrings aus dem gegebenen String s, sortiert diese, verknüpft sie, und gibt das Zeichen an Indexposition m aus … (das hätte ich vielleicht dazuschreiben sollen.)

Beispiel:

s=acb und m=7.

Die Substrings sind: acb a ac c cb und b. Sortiert: aacacbbccb. Es würde also c zurückgegeben werden (die Indizes sind 0-basiert).

7

Ok … Der String s hat die Länge n. Es gibt n*n/2 Teilstrings vom String s. Das Einfügen in die TreeSet kostet log(n). Zusammen wären das n*n*log(n)/2. Das wäre theoretisch O(n*n*log(n)) >= O(n^2).

Es gibt aber ein Problem. Zwei Teilstrings können nicht mit konstanter Zeit miteinander verglichen werden. Somit würde ein Einfügen in die TreeSet log(n * x) kosten. x ist wiederum von der Länge der Teilstrings abhängig. Nehmen wir (vereinfachend) x=n an. Dann ergibt sich n*n*log(n*n)/2 … und das wäre nicht mehr O(n^2), denke ich.

Hab ich mich verrechnet?

9

Hm, hat denn niemand eine Idee? Oder hab ich so unverständlich formuliert?.. :frowning:

Oder… werde ich inzwischen von allen gehasst?