Berapa lama rekursi Collatz berjalan?

19

Saya memiliki kode Python berikut.

def collatz(n):
    if n <= 1:
        return True
    elif (n%2==0):
        return collatz(n/2)
    else:
        return collatz(3*n+1)

Berapa waktu berjalan dari algoritma ini?

Mencoba:

Jika menunjukkan waktu fungsi berjalan . Maka saya pikir saya memiliki $T(n)$ collatz(n)

{\begin{cases} T (n) = 1 for n \leq 1 \\ T (n) = T (n / 2) for n even \\ T (n) = T (3 n + 1) for n odd \end{cases}

$\begin{cases} T(n)=1 \text{ for } n\le 1\\ T(n)=T(n/2) \text{ for } n\text{ even}\\ T(n)=T(3n+1) \text{ for } n\text{ odd}\\ \end{cases}$

Saya pikir akan menjadi jika adalah genap tetapi bagaimana menghitung pengulangan secara umum? $T(n)$ $\lg n$ $n$

algorithm-analysis runtime-analysis recurrence-relation 9bi7
sumber

4

Itu harus

dan seterusnya. +1 itu penting, jika tidak, Anda harus

T (n) = T (\frac{n}{2}) + 1

$T(n) = T(\frac n2) + 1$

, untuk semua

yang diakhiri urutannya.

T (n) = 1

$T(n) = 1$

n

$n$

user253751

2

54 genap, T (54) = 112! =

Lg

Apakah diasumsikan bahwa pengguna hanya akan memasukkan bilangan bulat?

Dean MacGregor

@DeanMacGregor Ya. Bahkan, bilangan bulat positif diasumsikan.

duskwuff

lebih banyak detail bkg akan sangat membantu. dari mana Anda mendapatkan kode itu, bagaimana Anda diperkenalkan dengannya? ini adalah masalah terbuka semifamous dalam teori bilangan yang tidak terpecahkan selama ~ ¾ abad di mana seluruh buku karya Lagarias telah ditulis. dari CS pov membuktikan itu di setiap waktu atau ruang kompleksitas kelas setara dengan bukti. banyak lagi referensi di sini . juga topik yang bagus untuk Obrolan Ilmu Komputer bagi siapa pun yang tertarik. ada juga collatztag di MathOverflow dll. penelitian terbaru menunjukkan masalah memiliki kualitas fraktal intrinsik membuatnya sulit.

vzn

29

Ini adalah dugaan Collatz - masalah masih terbuka.
Dugaan adalah tentang bukti bahwa urutan ini berhenti untuk input apa pun, karena ini tidak terselesaikan, kita tidak tahu bagaimana menyelesaikan hubungan pengulangan runtime ini, apalagi itu mungkin tidak berhenti sama sekali - jadi sampai terbukti, waktu berjalan tidak diketahui dan mungkin . $\infty$

Jahat
sumber

Terima kasih. Tapi rekursi saya benar, kan? Jika demikian, maka kita masih tidak dapat menemukan solusi untuk rekursi itu?

9bi7

Apa yang Anda maksud dengan "rekursi itu benar"? Anda tidak dapat menemukan waktu berjalan, tetapi untuk banyak angka ini akan membuat beberapa lompatan dan mencapai 1.

tidak menunjukkan runtime tetapi fungsinya sendiri.

T (n)

$T(n)$

Jahat

Dengan benar saya maksudkan misalnya seperti dalam semacam gabungan kita bisa mendapatkan

T (n) = 2 T (n / 2) + O (n)

$T(n)=2T(n/2)+O(n)$ . Karena kode bersifat rekursif, kita dapat menulis perulangan untuk itu, bukan?

9bi7

7

"Karena ini tidak terselesaikan, tidak ada batas atas" - kita harus berhati-hati dengan bahasa di sini. Kita tidak tahu solusi dari perulangan ini, akhir dari cerita.

Raphael

7

\exists

$\exists$

15

Anda menerjemahkan kode dengan benar . Ada banyak metode untuk menyelesaikan perulangan .

Namun, saat ini tidak diketahui apakah collatzbahkan berhenti untuk semua n; klaim yang dilakukannya dikenal sebagai dugaan Collatz . Oleh karena itu, tidak ada metode yang dikenal akan bekerja pada perulangan ini.

$T(n)$ $\lg n$ $n$

$n=2^k$ $\Theta$

Raphael
sumber

13

Fungsi kompleksitas waktu adalah

{\begin{cases} T (n) = HAI (1) untuk n \leq 1 \\ T (n) = T (n / 2) + HAI (1) untuk n bahkan \\ T (n) = T (3 n + 1) + HAI (1) untuk n aneh \end{cases}

$\begin{cases} T(n)= O(1) \text{ for } n\le 1\\ T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\ T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\ \end{cases}$

yang dapat ditulis ulang sebagai berikut jika Anda tertarik pada kompleksitas waktu asimptotik.

{\begin{cases} T (n) = 1 for n \leq 1 \\ T (n) = T (n / 2) + 1 for n even \\ T (n) = T (3 n + 1) + 1 for n odd \end{cases}

$\begin{cases} T(n)= 1 \text{ for } n\le 1\\ T(n)=T(n/2) + 1 \text{ for } n\text{ even}\\ T(n)=T(3n+1) + 1\text{ for } n\text{ odd}\\ \end{cases}$

$\langle M,1^n\rangle \in Halt$ $n$ $n$

Dugaan Collatz adalah dugaan yang sangat terkenal yang diusulkan Collatz pada tahun 1937. Banyak matematikawan terkemuka telah menghabiskan (baca terbuang) berjam-jam dalam mencoba untuk menyelesaikan dugaan ini tetapi sedikit berhasil. Bahkan Paul Erds berkata tentang dugaan Collatz, "Matematika belum siap untuk masalah seperti itu."

Shreesh
sumber

1

"terbuang" adalah penilaian subyektif. lihat analisis ahli oleh Lagarias untuk alasan mengapa hasil kerja / sebagian pada dugaan dapat dianggap sebagai tidak "terbuang". juga kutipan oleh Erdos mungkin beberapa dekade dan matematika telah berkembang secara substansial sejak itu, dan terus ... dan kemungkinan tidak semua teknik matematika baru telah diupayakan melawan masalah tersebut.

vzn

Itu adalah lidah di komentar pipi. (Agar adil saya memasukkannya ke dalam kurung, bukan). Sampai masalah terpecahkan, semua upaya tampaknya sia-sia, tetapi begitu diselesaikan, Anda melihat bagaimana bahkan kegagalan tersebut telah mengarah ke solusi. Dan saya tidak setuju dengan Anda bahwa matematika telah berkembang secara substansial; teknologi telah berkembang secara substansial, tetapi fisika, matematika, dan bahkan ilmu komputer mengalami kemajuan secara perlahan, dan begitulah seharusnya (saya dapat mengatakan ini karena, saya yang telah mempelajari tali saya 30 tahun yang lalu, masih tidak merasa ketinggalan zaman).

Shreesh

3 x + 1

$3x+1$

Lagarias menulis / menyusun / mengedit seluruh buku tentang masalah ini dan kedengarannya "meminta maaf" tentang mempelajari masalahnya? lol! justru sebaliknya . namun setuju / mengakui bahwa dia memiliki posisi bertahan karena banyak matematikawan lain tidak menganggap masalah ini penting atau layak untuk diserang / diusahakan besar (dan perhatikan gauss merasakan hal yang persis sama tentang Fermats Last Thm!). tetapi ada banyak kasus besar matematikawan papan atas menganggapnya serius misalnya Tao untuk satu.

vzn

2

$n$ $odd$ $n$ $3n+1$ ). Jadi ada lebih banyak pekerjaan yang harus dilakukan pada cabang perhitungan itu.

$T(n) = 2T(n/2) +n$ $T(0)$ $T(1)$

$3n+1$

Sorrop
sumber

0

Anda memiliki T (n) = T (n / 2) + 1 jika n adalah genap. Tapi kemudian n / 2 sangat mungkin bahkan tidak, jadi Anda terjebak di sana.

Yang terjadi adalah bahwa aturan kecil yang Anda pelajari dihadapkan pada masalah nyata, dan aturan itu tidak berfungsi. Mereka menabrak dinding bata, muka terlebih dahulu, dan itu menyakitkan. Bantulah diri Anda sendiri, dan ikuti rekursi untuk T (7) secara manual, dan kemudian Anda memberi tahu jika Anda masih yakin ini terkait lg n.

Jika Anda berpikir ini tidak terkait dengan pertanyaan asli karena 7 tidak genap: Kapanpun n ganjil, T (n) = T (3n + 1), dan 3n + 1 adalah genap, jadi jika T (n) dicatat n jika n adalah genap, itu akan menjadi log (3n + 1) + 1 setiap kali n> 1 ganjil.

gnasher729
sumber

Berapa lama rekursi Collatz berjalan?

Jawaban: