La complessità temporale di questa funzione è (n)? Può essere ottimizzato ulteriormente?

Dato il tuo codice di esempio, suppongo che la seguente ipotesi sia vera:

• str contiene solo valori di carattere da 'a' a 'z'

Dato che, possiamo immediatamente vedere un'opportunità di ottimizzazione: se str.Length è maggiore di charfound.Length , ci sarà un carattere duplicato, quindi possiamo includere un controllo per quello all'inizio della funzione.

public class Program
{
    public static void Main(string[] args)
    {
        DuplicateChars(args[0].ToLower());
    }

    public static bool DuplicateChars(string str)
    {
        bool[] charfound = new bool[26];
        int index = 0;

        if(str.Length > charfound.Length) return true;

        for(int i = 0; i <= str.Length ; ++i)
        {
            index = (byte)(str[i]);
            //subtract by ascii value of small a 97.
            index -= 97;
            if(charfound[index])
                return true;
            else
                charfound[index] = true;
        }  

        return false;
    }
}

Dopo questa modifica, l'input peggiore sarebbe una stringa che consiste in una permutazione di "abcdefghijklmnopqrstuvwxyz" , il che significherebbe che la funzione è O (1) nel peggiore dei casi. (Prova di ciò è lasciato come esercizio per il lettore.)

EDIT: come sottolineato da @Pieter B nei commenti, probabilmente vorrai spostare la chiamata a ToLower() da Main a destra dopo la riga if(str.Length > charfound.Length) return true; in modo da non spendere O (n ) tempo in totale.

Puoi migliorarlo se hai ulteriori informazioni sulla dimensione del tuo alfabeto.

Supponiamo che la tua stringa possa avere SOLO caratteri ASCII. Ciò significa che puoi avere al massimo 128 caratteri unici nella tua stringa. Qualsiasi stringa con più di 128 caratteri avrà caratteri duplicati.

Ciò significa che devi solo eseguire DuplicateChars se la lunghezza della stringa è minore o uguale a 128, che pone un limite superiore costante su n e rende l'algoritmo O (1).

Ancora O (n) ma molto meno codice

public static bool StringHasDup(string s)
{
    return (s.Length != new HashSet<char>(s.ToCharArray()).Count);
}