Two-Sum - Pre-sort Optimization Algorithm Design

Question

🧩 Apakah mungkin untuk mengoptimalkan runtime dari solusi dua-jumlah dengan menerima masukan yang telah diurutkan sebelumnya baik dalam urutan menaik atau menurun?

🚀 Dua Jumlah Asli

Tentukan apakah ada dua item yang kapasitas individualnya akan sama dengan total kapasitas sambil memastikan item yang sama tidak dapat dipilih dua kali.

• Input: Int mewakili kapasitas total dan Array of Int merepresentasikan kapasitas individu item.
• Keluaran: Boolean yang menunjukkan apakah mungkin dua item sama dengan kapasitas total.
• Kompleksitas waktu: Pertumbuhan linier, $O(n)$
• Kompleksitas ruang: Pertumbuhan linier, $O(n)$

Sampel

Memasukkan: [4, 5, 2, 6]

• Kapasitas total: 10
• Mengharapkan: true

Memasukkan: [4, 5, 2, 5]

• Kapasitas total: 10
• Mengharapkan: true

Memasukkan: [4, 5, 2, 7]

• Kapasitas total: 10
• Mengharapkan: false

Pseudocode

1. Buat Set searchSetuntuk menyimpan item yang sudah diperiksa.

2. Iterasi melalui input Array of item capacity.

   2a. Temukan targetCapacityuntuk item saat ini:totalCapacity - itemCapacity

   2b. Jika searchSetberisi targetCapacity, return true.

   2c. Lain, tambahkan itemCapacityke searchSet.

3. Kembalikan falsejika seluruh masukan diiterasi tanpa menemukan kecocokan.

🏗️ Pra-Sortir

1. Simpan var baru lastTargetCapacity
2. Jika arus itemCapacity< lastTargetCapacity, tidak ada kemungkinan dua penjumlahan dan pengembalian false.

yaitu

Memasukkan: [6,2,1,0]

• Kapasitas total: 9

Iterasi

1. targetCapacity = 9 - 6, lastTargetCapacity= 3
2. Kembalikan salah karena itemCapacitydari 2< lastTargetCapacitydari 3.

Answer 1

Solusi Two Sum dapat dioptimalkan untuk kinerja runtime mengingat Array input telah diurutkan sebelumnya dalam urutan naik atau turun.

Jika Pencarian Biner digunakan untuk menemukan hal di targetCapacityatas, itu akan berjalan dalam logaritmik,$O(logn)$, waktu proses rata-rata. Ini lebih cepat daripada pseudocode di atas yang berjalan secara linier,$O(n)$, waktu proses menggunakan iterasi dan hashing.

Jika penyortiran tidak disediakan dalam input maka tidak mungkin untuk mengurutkan dan mencari lebih cepat dari $O(n)$. Yang terbaik yang bisa dilakukan adalah$O(nlogn)$ dengan strategi seperti Quicksort dan Binary Search.

Lihat: Stanford - Penjelasan Dua Jumlah

Answer 2

Ya, Anda bisa menyelesaikan soal dua-jumlah dalam $O(n)$waktu, jika nomor disajikan dalam urutan yang diurutkan. Lihat jawaban saya yang lain untuk mengetahui cara melakukannya; ini melibatkan pemindaian linier. Ini optimal secara asimtotik, seperti yang sudah diperlukan$O(n)$ waktu bahkan untuk membaca masukan, dan memecahkan masalah mungkin memerlukan membaca seluruh masukan, sehingga tidak ada perbaikan asimtotik lebih lanjut.