Care este timpul de execuție al String.toCharArray()? (Programare, Java, String, Copie, Timp De Execuție, Sistem)

pâine prăjită cu scorțișoară a intrebat.

Care este timpul de execuție al lui String.toCharArray() în java? Codul sursă este

 public char[] toCharArray() {
    // Cannot use Arrays.copyOf because of class initialization order issues
    char result[] = new char[value.length];
    System.arraycopy(value, 0, result, 0, value.length);
    return result;
}

Are System.arrayCopy? are timpul de execuție de O(n)? Codul sursă nu spune prea multe despre cum este implementat. Trece prin fiecare element și îl copiază? Mulțumesc.

Comentarii

  • Sunt foarte sigur că timpul de execuție este O(n) nu poate fi mai bun (caracterele trebuie copiate). Întrebarea este care este factorul. –  > Por MrSmith42.
  • Vezi acest răspuns: stackoverflow.com/a/11208577/485971 –  > Por irrelephant.
  • @irrelephant Deci, probabil că este O(1)? Din moment ce nu este iterația printr-o buclă, ci copierea unui bloc de memorie? –  > Por Cinnamon toast.
  • Nu chiar – cred că este încă O(N), dar cu un factor constant scăzut, așa cum spune @MrSmith42. Uneori poate avea un factor constant mai mare – vezi stackoverflow.com/a/2589962/485971 -.  > Por irrelephant.
  • @cinnamontoast: Chiar dacă metoda copiază blocuri de memorie, tot nu poate fi O(1). Aș spune că timpul de execuție este încă O(N), , unde N este numărul de blocuri. Deși este o abordare mai rapidă, tot trebuie să copiați toate blocurile. –  > Por Chris Dargis.
1 răspunsuri
NPE

System.arraycopy() este de obicei un intrinsec și este foarte rapid. Acestea fiind spuse, tot trebuie să se uite la (și să copieze) fiecare element al tabloului, astfel încât complexitatea sa asimptotică este liniară în lungimea tabloului, adică O(n).

Prin urmare, complexitatea lui toCharArray() este O(n), , unde n este lungimea șirului.