Bagaimana cara mengembangkan algoritma memecahkan masalah 2-jumlah?

Diberikan array bilangan bulat yang diurutkan, saya ingin menemukan jumlah pasangan yang berjumlah . Misalnya, mengingat , jumlah pasangan yang dijumlahkan menjadi nol adalah . $0$ $\{-3,-2,0,2,3,4\}$ $2$

Misalkan adalah jumlah elemen dalam array input. Jika saya menggunakan pencarian biner untuk menemukan invers terbalik untuk elemen dalam array, urutannya adalah . Jika saya melintasi semua elemen di set, maka urutannya adalah . $N$ $O(\log N)$ $O(N\log N)$

Bagaimana menemukan algoritma yang orde ? $O(N)$

algorithms Laura
sumber

Masalah -SUM biasanya merujuk masalah yang sedikit berbeda, di mana orang mencoba untuk menemukan satu set elemen dari array input sedemikian rupa sehingga jumlahnya menjadi nol. Dalam model komputasi tertentu, tidak mungkin untuk mendapatkan algoritma waktu linier untuk , atau bahkan . Lihat pertanyaan ini .

k

$k$

k

$k$

A

$A$

k = 2

$k=2$

k

$k$

Juho

Jawaban:

Biarkan menjadi array input yang diurutkan. Menjaga dua pointer dan yang masuk melalui elemen-elemen di . Pointer akan melewati "bagian kiri" dari , yaitu bilangan bulat negatif. Pointer melakukan hal yang sama untuk "bagian kanan", bilangan bulat positif. Di bawah ini, saya akan menguraikan solusi pseudocode dan menganggap bahwa untuk kesederhanaan kecil. Dihilangkan juga pemeriksaan untuk kasus-kasus di mana hanya ada positif atau hanya bilangan bulat negatif dalam . $A$ $l$ $r$ $A$ $l$ $A$ $r$ $0 \notin A$ $A$

COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l]) 
     --left;
   else 
     ++right;

Jelas algoritma membutuhkan waktu . $O(N)$

Juho
sumber

Anda mungkin harus menambahkan argumen untuk kebenaran.

Raphael

-1

Pendekatan paling sederhana, menurut pemahaman saya, tampaknya menggunakan Tabel-Hash, H = {a [0] = true, .., a [n-1] = true}. Hash-Table ini dapat dibangun dalam waktu O (n). Setelah Tabel-Hash dibuat, lakukan iterasi melalui A [0, .., n-1] dan periksa apakah H [-1 * a [i]] ada. Jika ya, tambahkan penghitung sebanyak 1, dan kembalikan hasil akhirnya. Ini jelas O (n).

Juspreet Sandhu
sumber

Ekspresi H = {a [0] = true, .., a [n-1] = true} dan A [0, .., n-1] tidak masuk akal bagi saya. Saat menggunakan fungsi hash, array tidak harus disortir. Tetapi algoritma yang menggunakan fungsi hash menggunakan beberapa sifat pseudorandom dari fungsi hash. Dalam kasus terburuk, semua item akan dipetakan ke nilai hash yang sama dan algoritmanya kuadratik. Saya tidak tahu apa persyaratan OP.

miracle173

Lihat implementasi saya di bawah ini dan katakan padaku bagaimana kuadratik dalam kasus terburuk.

sammy

@ miracle173: Itu hanya kenyamanan untuk notasi. Saya dapat mewakili Hash-Table sebagai satu set pasangan Key-Value (yang sebenarnya, secara matematis). Pengaturan aktual dalam memori tidak perlu untuk rincian teoritis tentang kompleksitas. Dan, fungsi Hash dirancang untuk menghindari tabrakan asalkan cukup entropi benih. Saya menjawab dengan karena jawaban Juho mengasumsikan "diurutkan A", yang secara implisit membuat kompleksitas O (n log (n)) dan * BUKAN O (n).

Juspreet Sandhu

@ manbearpig1 Pengguna Jahat sudah menambahkan komentar ke posting Anda yang seharusnya menjawab pertanyaan Anda. Kasus terburuk dari pencarian tabel hash adalah O (n) dan oleh karena itu kasus terburuk dari keseluruhan algoritma adalah O (n ^ 2).

miracle173

@JuspreetSandhu Usere Evil menambahkan komentar ke jawaban lain yang menjelaskan masalah dengan fungsi hash.

miracle173

-1

Perhatikan bahwa kita dapat mencari nilai dalam Python yang diset dalam waktu konstan.

def twoSum(data):
    count = 0
    nums = set()
    for num in data:
        if (num * -1) in nums:
            count += 1
        nums.add(num)
    return count

sammy
sumber

Ini bukan waktu yang konstan tetapi waktu yang diharapkan konstan. Mungkin ada tabel hash, pohon (diri) seimbang atau struktur serupa. Ini memberikan diharapkan tetapi mungkin dalam kasus terdegradasi untuk tabel hash atau untuk pohon. Selain itu di sini kami lebih suka kodesemu karena tidak semua orang mengerti python, jadi tidak jelas mengapa atau bagaimana cara kerjanya. Dalam kasus terburuk untuk tabel hash di mana setiap nilai dipetakan ke dalam satu bin, waktu untuk mendapatkan elemen adalah . Anda melakukan langkah ini kali sehingga memberikan dalam kasus terburuk.

O (1)

$\mathcal O(1)$

O (n)

$\mathcal O(n)$

O (\log n)

$\mathcal O(\log n)$

O (n)

$\mathcal O(n)$

n

$n$

O (n^{2})

$\mathcal O(n^2)$

Evil