Apa kompleksitas fungsi pemisahan string Java?

8

String saya adalah tipe "abacsdsdvvsg"atau "a a a a a a a"
Dan saya menggunakan String[] stringArray = s.split("");atau String[] stringArray = s.split(" ");
saya bertanya-tanya apa yang akan menjadi kompleksitas (dalam O(string length)) untuk pemisahan di atas?
PS: Saya tahu cara menghitung O (...) jika kode diberikan. Di sini saya tidak tahu algoritma fungsi split.

java strings java8 tezz
sumber
Kemungkinan duplikat dari Apa itu O (...) dan bagaimana cara menghitungnya?
Agak
Karena saya tidak tahu algo fungsi split, saya tidak berpikir itu pertanyaan rangkap @gnat
tezz

Jawaban:

7

Kompleksitas akan tergantung pada regex yang Anda gunakan untuk melakukan pemisahan. (Ya, argumen yang Anda berikan ke String.split (...) adalah regex!)

Sebagai contoh Anda, itu akan menjadi di O(N)mana Njumlah karakter dalam String input.

Algoritma split cukup mudah, berdasarkan implementasi regex yang ada. Deskripsi tingkat tinggi adalah:

  1. Kompilasi regex dan buat korek api
  2. Iterate atas string:
    1. Gunakan Matcher.find(...)untuk menemukan batas kata berikutnya
    2. Gunakan String.substring untuk mengekstrak kata
    3. Tambahkan kata ke daftar string
  3. Konversi daftar string ke array string.

Pencarian untuk jeda antara "kata" akan menjadi O(N)atau lebih kompleks, tergantung pada regex ( findpanggilan). Konstruksi daftar, susunan hasil, dan substring akan menjadi O(N)yang terburuk.

Detail tepatnya ada di kode sumber, yang dapat Anda temukan menggunakan Google. (Cari "java.lang.String" source, pilih satu dan kemudian telusuri ke versi Java yang Anda minati. Atau cari file dalam kode sumber file ZIP yang termasuk dalam instalasi JDK Anda)

Stephen C
sumber
3

Ini O (n) dalam kasus-kasus khusus Anda, tempat Anda memisahkan dengan 1/0 pemisah panjang karakter. Secara umum, itu O (n + k) dengan pemisah k-karakter, dapat diimplementasikan menggunakan algoritma KMP. Java string split juga menerima regex sebagai seperator, dalam hal ini kompleksitasnya tergantung pada algoritma pencocokan yang digunakan. Salah satu algoritma pencocokan regex yang umum adalah algoritma Thompson NFA.

Vinyleem
sumber