Frage Zeitkomplexitätsberechnung für meinen Algorithmus


Gegeben eine Zeichenkette, finde das erste sich nicht wiederholende Zeichen und gib ihren Index zurück. Wenn es nicht existiert, gebe -1 zurück. Sie können annehmen, dass die Zeichenfolge nur Kleinbuchstaben enthält.

Ich werde einen Hash definieren, der das Auftreten von Zeichen verfolgt. Durchstreichen Sie den String von links nach rechts, überprüfen Sie, ob das aktuelle Zeichen im Hash enthalten ist, fahren Sie fort, falls ja, andernfalls durchlaufen Sie in einer anderen Schleife den Rest des Strings, um zu sehen, ob das aktuelle Zeichen existiert. Wenn nicht, den Index zurückgeben und den Hash aktualisieren, falls er existiert.

def firstUniqChar(s):

    track = {}
    for index, i in enumerate(s):
        if i in track:
            continue
        elif i in s[index+1:]: # For the last element, i in [] holds False
            track[i] = 1
            continue
        else:
            return index
    return -1

firstUniqChar('timecomplexity')

Wie hoch ist die zeitliche Komplexität (Durchschnitt und schlechteste) meines Algorithmus?


5
2017-08-23 03:50


Ursprung


Antworten:


Ihr Algorithmus hat eine Zeitkomplexität von O(kn) woher k ist die Anzahl der eindeutigen Zeichen in der Zeichenfolge. Ob k ist eine Konstante, dann ist es O(n). Da die Problembeschreibung die Anzahl der Alternativen für Elemente ("Kleinbuchstaben (ASCII)" annehmen) eindeutig begrenzt k ist konstant und Ihr Algorithmus läuft hinein O(n) Zeit für dieses Problem. Auch wenn n zu unendlich wachsen wird, wirst du nur machen O(1) Scheiben der Saite und Ihr Algorithmus bleiben erhalten O(n). Wenn Sie entfernt haben trackDann wäre es O(n²):

In [36]: s = 'abcdefghijklmnopqrstuvwxyz' * 10000

In [37]: %timeit firstUniqChar(s)
100 loops, best of 3: 18.2 ms per loop

In [38]: s = 'abcdefghijklmnopqrstuvwxyz' * 20000

In [37]: %timeit firstUniqChar(s)
10 loops, best of 3: 36.3 ms per loop

In [38]: s = 'timecomplexity' * 40000 + 'a'

In [39]: %timeit firstUniqChar(s)
10 loops, best of 3: 73.3 ms per loop

Es hält so ziemlich das da T(n) ist immer noch von O(n) Komplexität - es skaliert genau linear mit der Anzahl der Zeichen in der Zeichenfolge, obwohl dies das Worst-Case-Szenario für Ihren Algorithmus ist - es gibt kein einzelnes Zeichen, das einzigartig ist.


Ich werde hier eine nicht so effiziente, aber einfache und intelligente Methode vorstellen; Zählen Sie das Zeichenhistogramm zuerst mit collections.Counter; dann iteriere über die Charaktere, die den einen finden

from collections import Counter
def first_uniq_char_ultra_smart(s):
    counts = Counter(s)
    for i, c in enumerate(s):
        if counts[c] == 1:
            return i

    return -1

first_uniq_char('timecomplexity')

Dies hat zeitliche Komplexität von O(n); Counter zählt das Histogramm in O(n) Zeit und wir müssen die Zeichenfolge erneut für aufzählen O(n) Figuren. In der Praxis glaube ich jedoch, dass mein Algorithmus niedrige Konstanten hat, weil er ein Standardwörterbuch für verwendet Counter.

Und machen wir einen sehr dummen Brute-Force-Algorithmus. Da Sie annehmen können, dass die Zeichenfolge nur Kleinbuchstaben enthält, verwenden Sie diese Annahme:

import string
def first_uniq_char_very_stupid(s):
    indexes = []
    for c in string.ascii_lowercase:
        if s.count(c) == 1:
            indexes.append(s.find(c))

    # default=-1 is Python 3 only
    return min(indexes, default=-1)

Lassen Sie mich meinen Algorithmus und einige Algorithmen in den anderen Antworten auf Python 3.5 testen. Ich habe einen Fall gewählt, der pathologisch schlecht ist meine Algorithmus:

In [30]: s = 'timecomplexity' * 10000 + 'a'

In [31]: %timeit first_uniq_char_ultra_smart(s)
10 loops, best of 3: 35 ms per loop

In [32]: %timeit karin(s)
100 loops, best of 3: 11.7 ms per loop

In [33]: %timeit john(s)
100 loops, best of 3: 9.92 ms per loop

In [34]: %timeit nicholas(s)
100 loops, best of 3: 10.4 ms per loop

In [35]: %timeit first_uniq_char_very_stupid(s)
1000 loops, best of 3: 1.55 ms per loop

Also, mein blöder Algorithmus ist der schnellste, weil er das findet a am Ende und packt aus. Und mein intelligenter Algorithmus ist am langsamsten. Ein weiterer Grund für die schlechte Performance meines Algorithmus ist neben dem schlimmsten Fall der OrderedDict ist in C auf Python 3.5 und geschrieben Counter ist in Python.


Lassen Sie uns hier einen besseren Test machen:

In [60]: s = string.ascii_lowercase * 10000

In [61]: %timeit nicholas(s)
100 loops, best of 3: 18.3 ms per loop

In [62]: %timeit karin(s)
100 loops, best of 3: 19.6 ms per loop

In [63]: %timeit john(s)
100 loops, best of 3: 18.2 ms per loop

In [64]: %timeit first_uniq_char_very_stupid(s)
100 loops, best of 3: 2.89 ms per loop

So scheint es, dass der "dumme" Algorithmus von mir überhaupt nicht so dumm ist, er nutzt die Geschwindigkeit von C, während er die Anzahl der Iterationen des ausgeführten Python-Codes minimiert, und gewinnt in diesem Problem eindeutig.


9
2017-08-23 05:18



Wie andere bemerkt haben, ist Ihr Algorithmus O(n²) aufgrund der verschachtelten linearen Suche. Wie von @Antti entdeckt, ist der Algorithmus des OP linear und gebunden O(kn) zum kals die Anzahl aller möglichen Kleinbuchstaben.

Mein Vorschlag für ein O(n) Lösung:

from collections import OrderedDict

def first_unique_char(string):
    duplicated = OrderedDict()  # ordered dict of char to boolean indicating duplicate existence
    for s in string:
        duplicated[s] = s in duplicated

    for char, is_duplicate in duplicated.items():
        if not is_duplicate:
            return string.find(char)
    return -1

print(first_unique_char('timecomplexity'))  # 4

6
2017-08-23 04:50



Ihr Algorithmus ist O (n2), weil Sie eine "versteckte" Iteration über eine Scheibe von haben s innerhalb der Schleife vorbei s.

Ein schnellerer Algorithmus wäre:

def first_unique_character(s):
    good = {} # char:idx
    bad = set() # char
    for index, ch in enumerate(s):
        if ch in bad:
            continue
        if ch in good: # new repeat
            bad.add(ch)
            del good[ch]
        else:
            good[ch] = index

    if not good:
        return -1

    return min(good.values())

Dies ist O (n), weil die in Nachschlagevorgänge verwenden Hashtabellen, und die Anzahl der einzelnen Zeichen sollte wesentlich geringer sein als len(s).


4
2017-08-23 04:03