ForHosting KIT · Strumenti per sviluppatori

Confronti del merge sort: caso peggiore e medio

Questo calcolatore stima quanti confronti tra elementi esegue un merge sort top-down standard su n elementi.

● BetaGratis · nel tuo browser

Usalo da WebAPIEmailTelegramApp presto

Restituisce il conteggio esatto del caso peggiore, il valore atteso per un ordinamento casuale uniforme, i livelli di fusione ricorsiva e n moltiplicato per il logaritmo in base 2 di n come riferimento. Lei può così osservare concretamente la crescita linearitmica e distinguerla da quella quadratica.

Che cosa viene conteggiato

Il calcolo considera i confronti di ordinamento tra elementi durante la fusione, operazione centrale nell’analisi tradizionale del merge sort. Non include verifiche degli indici, assegnazioni, scritture in array temporanei, chiamate ricorsive, allocazioni o il lavoro interno di un comparatore personalizzato. Un solo elemento non richiede confronti. Per input più grandi, l’algoritmo divide l’intervallo, ordina le due parti e confronta ripetutamente i primi elementi non ancora consumati. La fusione di gruppi con a e b elementi richiede al massimo a più b meno uno confronti, perché l’ultimo elemento rimasto può essere copiato direttamente. Il caso peggiore applica questa regola all’albero di suddivisione effettivo, anche quando n non è una potenza di due. Usi quindi n_log2_n come riferimento di scala e gli altri campi come stime operative.

Come si ricavano caso peggiore e media

La formula esatta del caso peggiore è n per il limite superiore del logaritmo in base 2 di n, meno due elevato a tale limite, più uno. Descrive un merge sort binario standard con sottoarray divisi nel modo più equilibrato possibile. La media è un valore atteso sulle permutazioni uniformemente casuali di chiavi distinte. Per fondere sequenze di a e b elementi, l’attesa è a più b, meno a diviso b più uno, meno b diviso a più uno. Il calcolatore somma ricorsivamente il costo sullo stesso albero bilanciato e arrotonda solo il risultato visualizzato a sei decimali. Un valore atteso può essere frazionario, anche se ogni esecuzione compie un numero intero di confronti. Duplicati, criteri di parità diversi, sequenze naturali o soglie per insertion sort possono modificare il conteggio osservato.

Come leggere il risultato linearitmico

Il valore n_log2_n mostra la scala linearitmica caratteristica. Ogni ulteriore livello di fusione elabora tutti gli n elementi, mentre il numero di livelli cresce soltanto in modo logaritmico. I due rapporti dividono le stime per n moltiplicato per il logaritmo in base 2 di n e mostrano quanto i conteggi concreti seguano il riferimento quando n è maggiore di uno. Sono descrittivi, non prove di complessità né benchmark hardware. Traffico di memoria, allocazioni, costo del comparatore, cache e runtime possono dominare il tempo reale. Provi valori subito sotto e sopra le potenze di due: in quei punti cambia la profondità ricorsiva e diventa evidente perché la notazione O grande ignora costanti e termini inferiori senza renderli irrilevanti per un input specifico.

Casi d'uso

Pianificare confronti costosi

Stimi le chiamate a un comparatore oneroso prima di un grande ordinamento stabile.

Spiegare la crescita algoritmica

Confronti i totali esatti con n per il logaritmo in base 2 di n.

Definire le attese dei test

Imposti un limite di caso peggiore per un’implementazione strumentata.

Domande frequenti

Che cosa significa confronto in questo caso?

È un confronto d’ordine tra elementi durante la fusione; gestione e spostamento dei dati sono esclusi.

Perché la media può essere frazionaria?

È il valore atteso su tutte le permutazioni casuali uniformi, non il conteggio di una singola esecuzione.

La stima include valori duplicati?

No. Il modello medio presuppone chiavi distinte; duplicati e pareggi possono cambiare il totale.

È un benchmark delle prestazioni?

No. Stima i confronti senza modellare memoria, processore, runtime, allocazioni o latenza.

Quale variante di merge sort viene modellata?

La variante binaria top-down standard, che divide ogni intervallo in parti il più possibile uguali.

Quanto costa una richiesta API?

Ogni richiesta API costa $0.002; il browser può usare la stessa logica deterministica.

Per sviluppatori — accesso via API

Tutto quello che vedi in questa pagina è disponibile anche via API. Questa sezione è per i team che vogliono integrarlo nei propri sistemi; chi non ne ha bisogno può semplicemente usare lo strumento qui sopra.

Endpoint

POSThttps://api.kit.forhosting.com/dev/merge-sort-comparisons

Autenticazione con Bearer token: un POST mette in coda l'attività e il risultato arriva via webhook o link firmato.

Chiamala dal tuo stack

curl -X POST https://api.kit.forhosting.com/dev/merge-sort-comparisons \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":8}'

const res = await fetch("https://api.kit.forhosting.com/dev/merge-sort-comparisons", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": 8
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/dev/merge-sort-comparisons",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": 8
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/merge-sort-comparisons", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":8}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":8}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/merge-sort-comparisons", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

Esempio di richiesta

{
  "n": 8
}

Esempio di risposta

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.merge_sort_comparisons",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

L'API è asincrona: ricevi subito un task_id e puoi fare polling fino a 1 richiesta al secondo.

Prezzi

per richiesta$0.002

Prezzo pubblicato, senza token né crediti. Se l'attività fallisce, non paghi.

Errori

HTTP	Codice	Significato
`401`	`unauthorized`	Chiave API mancante o non valida: controlla l'header Authorization.
`402`	`insufficient_balance`	Credito esaurito: ricarica per continuare a eseguire attività.
`404`	`unknown_type`	Tipo di attività sconosciuto: controlla il campo type della richiesta.
`429`	`rate_limited`	Troppe richieste in poco tempo: rallenta e riprova tra qualche secondo.

Leggi la documentazione completa del KIT →