Come identificate i casi "limite" sugli algoritmi?

20

In pratica come scopri quale potrebbe essere il tuo caso peggiore o migliore e qualsiasi altro caso "limite" che potresti avere PRIMA di averli e quindi, come ti prepari il codice?

    
posta Luis Armando 01.05.2011 - 05:47
fonte

5 risposte

23

In base al contenuto dell'algoritmo, puoi identificare quali strutture / tipi / costrutti di dati vengono utilizzati. Quindi, provi a capire i (possibili) punti deboli di questi e prova a elaborare un piano di esecuzione che lo eseguirà in quei casi.

Ad esempio, l'algoritmo prende una stringa e un intero come input e esegue l'ordinamento dei caratteri della stringa.

Qui abbiamo:

Stringa con alcuni casi speciali noti:

  • Stringa vuota
  • Stringa lunga
  • Stringa Unicode (caratteri speciali)
  • Se limitato a un set specifico di caratteri, cosa succede quando alcuni non si trovano nell'intervallo
  • Stringa di lunghezza pari / dispari
  • Null (come argomento)
  • Non terminato null

Integer con casi speciali noti:

  • 0
  • Min / MaxInt
  • Negativo / Positivo

Algoritmo di ordinamento che potrebbe non riuscire nei seguenti casi limite:

  • input vuoto
  • 1 elemento di input
  • Input molto lungo (forse di lunghezza massima (tipo di dati utilizzato per l'indice))
  • Garbage collection all'interno della raccolta che verrà ordinata
  • input nullo
  • Elementi duplicati
  • Raccolta con tutti gli elementi uguali
  • Inserimento dispari / pari lunghezza

Quindi, prendi tutti questi casi e crea una lunga lista cercando di capire come si sovrappongono. Es:

  • Il caso stringa vuoto copre il caso di raccolta vuoto
  • stringa null == raccolta null
  • ecc.

Ora crea casi di test per loro:)

Breve sommario : interrompi l'algoritmo in blocchi di base per i quali conosci i casi limite e poi li riassembla, creando casi limite globali

    
risposta data 01.05.2011 - 12:46
fonte
2

Non penso ci sia alcun algoritmo per determinare le condizioni del bordo .... basta sperimentare.

Esempio: per un parametro di byte vorresti testare numeri come 0, 127, 128, 255, 256, -1, qualsiasi cosa possa causare problemi.

    
risposta data 01.05.2011 - 06:22
fonte
2

Un "bordo" ha due significati, ed entrambi sono rilevanti quando si tratta di casi limite. Un bordo è un'area in cui un piccolo cambiamento nell'ingresso porta a un grande cambiamento nell'output o alla fine di un intervallo.

Quindi, per identificare i casi limite di un algoritmo, prima guardo il dominio di input. I suoi valori di bordo potrebbero portare a casi limite dell'algoritmo.

In secondo luogo, guardo il dominio di output e guardo indietro ai valori di input che potrebbero crearli. Questo è meno comunemente un problema con gli algoritmi, ma aiuta a trovare problemi negli algoritmi progettati per generare output che si estende su un determinato dominio di output. Per esempio. un generatore di numeri casuali dovrebbe essere in grado di generare tutti i valori di output previsti.

Infine, controllo l'algoritmo per vedere se ci sono casi di input che sono simili, ma che conducono a output diversi. Trovare questi casi limite è il più difficile, perché coinvolge entrambi i domini e una coppia di input.

    
risposta data 02.05.2011 - 15:18
fonte
0

Questa è una domanda molto generale, quindi tutto ciò che posso fare è buttare fuori alcune idee generiche e vaghe:)

: esamina i casi limite. Ex. se stai analizzando una stringa, cosa succede se la stringa è vuota o nulla? Se stai contando da x a y cosa succede a x e y?
-Code che potrebbe essere semplificato o D.R.Y.-out. Qualsiasi complessità non necessaria potrebbe aggiungere cose che potrebbero andare storte.

    
risposta data 01.05.2011 - 05:56
fonte
0

Parte della capacità di utilizzare algoritmi è conoscerne le debolezze e i casi patoligici. La risposta di Victor dà alcuni buoni consigli, ma in generale ti consiglierei di studiare l'argomento in modo più approfondito per avere un'idea di questo, non penso che tu possa seguire le regole empiriche per rispondere pienamente a questa domanda. Per esempio. vedi Cormen o Skiena (Skiena in particolare ha una sezione molto buona su dove usare gli algoritmi e ciò che funziona bene in certi casi, Cormen entra in più teoria credo).

    
risposta data 01.05.2011 - 12:52
fonte

Leggi altre domande sui tag