Kompleksitas ruang mengenali palindrom Watson-Crick

Saya memiliki masalah algoritmik berikut:

Tentukan ruang Turing kompleksitas mengenali string DNA yang merupakan palindrom Watson-Crick.

Palindrom Watson-Crick adalah string yang pelengkap terbalik adalah string asli. The pelengkap didefinisikan surat-bijaksana, terinspirasi oleh DNA: A adalah komplemen dari T dan C adalah komplemen dari G. Contoh sederhana untuk WC-palindrom adalah ACGT.

Saya telah menemukan dua cara untuk menyelesaikan ini.

Satu membutuhkan ruang.$\mathcal{O}(n)$

• Setelah mesin selesai membaca input. Rekaman input harus disalin ke rekaman kerja dalam urutan terbalik.
• Mesin kemudian akan membaca input dan bekerja kaset dari kiri dan membandingkan setiap entri untuk memverifikasi sel dalam rekaman kerja adalah pujian sel dalam input. Ini membutuhkan $\mathcal{O}(n)$ ruang.

Yang lain membutuhkan ruang $\mathcal{O}(\log n)$ .

• Saat membaca input. Hitung jumlah entri pada rekaman input.
• Ketika input tape selesai dibaca
  • salin pelengkap surat ke pita kerja
  • salin huruf L ke akhir kaset kerja
• (Loop point) Jika penghitung = 0, hapus worktape dan tulis ya, lalu berhenti
• Jika pita input bertuliskan L
  • Pindahkan kepala input ke kiri dengan jumlah yang ditunjukkan oleh penghitung (membutuhkan penghitung kedua)
• Jika pita input bertuliskan R
  • Pindahkan kepala input ke kanan dengan jumlah kali yang ditunjukkan oleh penghitung (membutuhkan penghitung kedua)
• Jika sel yang memegang nilai pada lembar kerja cocok dengan sel saat ini pada pita input
  • mengurangi counter dengan dua
  • Pindahkan satu ke kiri atau kanan tergantung apakah R atau L masing-masing ada di worktape
  • salin Komplemen L atau R ke lembar kerja sebagai pengganti L atau R saat ini
  • lanjutkan loop
• Jika nilai tidak cocok, kosongkan worktape dan tulis no, lalu hentikan

Ini muncul sekitar ruang untuk menyimpan kedua penghitung, komplemen saat ini, dan nilai L atau R.$2\log n+2$

Masalah saya

Yang pertama membutuhkan ruang dan waktu linear. Yang kedua membutuhkan waktu danlognruang. Saya diberi masalah dari kutipan dan muncul dengan dua pendekatan ini, tetapi saya tidak tahu harus memilih yang mana. Saya hanya perlu memberikan kompleksitas ruang masalah.$\frac{n^2}{2}$$\log n$

Alasan saya bingung

Saya akan cenderung mengatakan yang kedua adalah pilihan terbaik karena lebih baik dari segi waktu, tetapi jawaban itu hanya datang dari saya yang beruntung dan muncul dengan algoritma. Sepertinya jika saya ingin memberikan kompleksitas ruang pada sesuatu, itu tidak akan memerlukan keberuntungan untuk menghasilkan algoritma yang tepat. Apakah saya melewatkan sesuatu? Haruskah saya membuat solusi untuk masalah untuk menjawab kompleksitas ruang?

$\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$char

Untuk menunjukkan bahwa suatu masalah memiliki kompleksitas ruang tertentu, orang biasanya perlu membuat algoritma yang memiliki kompleksitas ruang tersebut. Ini mungkin memerlukan percobaan dan kesalahan, tetapi pendekatan yang lebih baik adalah memiliki pemahaman yang baik tentang masalah yang Anda lihat dan jumlah pengalaman yang baik dalam algoritma dan kompleksitas.

$O(n^2)$

Petunjuk: mengapa menggunakan ruang tambahan, ketika Anda bisa menggunakan ruang yang ditempati oleh input?

Petunjuk: zip bolak-balik melintasi string memeriksa satu karakter pada satu waktu - gunakan keadaan Mesin Turing untuk mengingat karakter mana yang Anda periksa dan hapus karakter yang sudah Anda periksa.

Cara pertanyaan diajukan Anda harus datang dengan batas atas dan batas bawah pada kompleksitas ruang.

$\mathcal{O}(\log n)$

$a^lb^{2l}a^l$$l$$\omega(1)$$\mathcal{O}(\log n)$

$c\cdot\Gamma^{s(n)}$$n$$\Gamma$$s(n)$$\Omega(\log n)$

Perhatikan bahwa Anda tidak perlu peduli dengan pelengkap huruf karena operasi ini sepele, jadi semua yang bekerja untuk palindrom biasa dapat dimodifikasi dengan beberapa negara lagi untuk menyelesaikan masalah Anda.

$S$$\Omega(n^2/S)$