Jumlah istilah Landau ditinjau kembali

Saya mengajukan pertanyaan (seed) tentang jumlah istilah Landau sebelumnya , mencoba untuk mengukur bahaya penyalahgunaan notasi asimtotik di aritmatika, dengan kesuksesan beragam.

Sekarang, di sini guru pengulangan kami, JeffE , pada dasarnya melakukan ini:

$\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n)$

Walaupun hasil akhirnya benar, saya pikir ini salah. Mengapa? Jika kita menambahkan semua keberadaan konstanta yang tersirat (hanya batas atas), kita miliki

$\qquad \displaystyle \sum_{i=1}^n c_i \cdot \frac{1}{i} \leq c \cdot H_n$ .

Sekarang bagaimana kita menghitung $c$ dari $c_1, \dots, c_n$ ? Jawabannya adalah, saya percaya, bahwa kita tidak dapat: $c$ harus terikat untuk semua $n$ tetapi kita mendapatkan lebih banyak $c_i$ saat $n$ tumbuh. Kami tidak tahu apa-apa tentang mereka; $c_i$ mungkin sangat bergantung pada $i$ , jadi kita tidak dapat mengasumsikan suatu ikatan: a terbatas $c$ mungkin tidak ada.

Selain itu, ada masalah halus yang variabelnya menuju hingga tak terbatas di sisi kiri - $i$ atau $n$ ? Kedua? Jika $n$ (demi kompatibilitas), apa arti dari $\Theta(1/i)$ , mengetahui bahwa $1 \leq i \leq n$ ? Apakah itu tidak hanya berarti $\Theta(1)$ ? Jika demikian, kami tidak dapat mengikat jumlah lebih baik dari $\Theta(n)$ .

Jadi, di mana itu meninggalkan kita? Apakah ini kesalahan yang mencolok? Yang halus? Atau itu hanya penyalahgunaan biasa notasi dan kita tidak harus melihat tanda-tanda seperti ini di luar konteks? Bisakah kita merumuskan aturan (yang benar) yang benar untuk mengevalutasikan (pasti) jumlah istilah Landau? $=$

Saya pikir pertanyaan utamanya adalah: apa yang ? Jika kita menganggapnya konstan (karena berada di dalam cakupan penjumlahan) kita dapat dengan mudah membangun contoh tandingan. Jika tidak konstan, saya tidak tahu cara membacanya. $i$

terminology asymptotics landau-notation Raphael
sumber

Pertanyaan tentang matematika ini. SE adalah bacaan yang baik tentang aritmatika dengan istilah Landau secara umum.

Raphael

\in

$\in$

Θ

$\Theta$

c = min (c_{1}, c_{2}, \dots, c_{n})

$c = \min(c_1, c_2, \cdots, c_n)$

C = max (c_{1}, c_{2}, \dots, c_{n})

$C = \max(c_1, c_2, \cdots, c_n)$

Tunggu sebentar, Bucky. Saya tidak menulis penjumlahan dengan Theta di dalamnya. Saya menulis perulangan dengan Theta di dalamnya. Apakah Anda benar-benar menafsirkan perulangan " " sebagai sesuatu selain "Ada fungsi sedemikian sehingga "?

t (n) = Θ (1 / n) + t (n - 1)

$t(n) = \Theta(1/n) + t(n-1)$

f \in Θ_{x \to \infty} (x \mapsto 1 / x)

$f \in \Theta_{x\to \infty}(x\mapsto 1/x)$

t (n) = f (n) + t (n - 1)

$t(n) = f(n) + t(n-1)$

JeffE

@ Raphael Tidak, perulangan tidak secara matematis sama dengan jumlah, untuk alasan yang Anda jelaskan! Perulangan memiliki tepat satu istilah Theta di dalamnya, yang jelas mengacu pada fungsi tunggal.

JeffE

Itu tidak terlalu intuitif - saya sangat tidak setuju, tapi saya pikir ini masalah selera dan pengalaman.

JeffE

Jawaban:

Tampak benar bagi saya dalam konvensi berikut:

$S_n = \sum_{k=1}^{n} \Theta(1/k)$ adalah notasi yang mudah digunakan

Ada (seperti ) sedemikian rupa $f(x) \in \Theta(1/x)$ $x \to \infty$

$S_n = \sum_{k=1}^{n} f(k)$ .

Jadi (atau dengan notasi dalam jawaban ini ) yang Anda dapatkan, tidak benar-benar bergantung pada . $c_i$ $c_k$ $k$

Di bawah interpretasi ini, memang benar bahwa . $S_n = \Theta(H_n)$

Bahkan, dalam jawaban Jeff, ia menunjukkan bahwa mana , sehingga konsisten dengan interpretasi di atas. $T(k+1) = f(k) + T(k)$ $f \in \Theta(1/k)$

Kebingungan tampaknya timbul dari mental "membuka gulungan" dan menganggap fungsi yang berbeda untuk setiap kemunculan ... $\sum$ $\Theta$

Aryabhata
sumber

Jup, tetapi setiap dapat memiliki fungsinya sendiri, dan konstan. Jadi konvensi ini hanya bekerja dengan konteks, yaitu jika kita tahu bahwa istilah Landau berasal dari definisi "seragam" (dalam dan ) yang agak seragam .

Θ

$\Theta$

k

$k$

n

$n$

Raphael

@ Raphael: Tampaknya tidak ada artinya membuka gulungan dan kemudian mengizinkan berbeda : konstanta kemudian akan tergantung pada variabel! dan itu menjadi penggunaan yang salah dari , dengan asumsi variabel adalah (atau dalam jawaban di atas). Bahkan jika kita mengasumsikan variabelnya adalah , masih terlihat tidak berarti bagi saya.

f_{i}

$f_i$

Θ

$\Theta$

Θ

$\Theta$

i

$i$

k

$k$

n

$n$

Aryabhata

Pada prinsipnya, setiap dapat memiliki konstan sendiri, tetapi dalam konteks tertentu Anda menjelaskan , jelas bahwa setiap tidak tidak memiliki konstan sendiri.

Θ

$\Theta$

Θ

$\Theta$

JeffE

@ Jeff: Benar. Kita dapat memiliki banyak dengan konstanta mereka sendiri, selama konstanta benar-benar konstan :-)

Θ

$\Theta$

Aryabhata

@ Jeff JEFE Jadi mengapa Anda tidak hanya menulis apa yang Anda maksud tetapi lebih suka sesuatu yang ambigu / salah? Perhatikan bahwa jawaban saya yang diperbarui sekarang mengusulkan cara untuk melakukannya. Saya menghargai komentar tentang itu; downvotes tanpa alasan tidak membantu saya memahami mengapa orang tampaknya menolak pendapat saya.

Raphael

Saya pikir saya telah menyelesaikan masalahnya. Intinya: menggunakan istilah Landau memisahkan variabel fungsi sumand dari variabel penjumlahan sum. Kami masih (ingin) membacanya sebagai identik, karena itu kebingungan.

Untuk mengembangkannya secara formal, apa yang dilakukannya

$\qquad \displaystyle S_n \in \sum_{i=1}^n \Theta(f(i)) \qquad \qquad\qquad (1)$

sangat jahat? Sekarang saya berasumsi bahwa ini membiarkan - bukan - hingga tak terbatas; jika kita membiarkan , setiap jumlah tersebut dievaluasi menjadi (jika penjumlahannya bebas dari dan karenanya konstan) yang jelas salah. Ini adalah hadiah pertama yang kita berikan pada hal-hal kasar: terikat (dan konstan) di dalam jumlah, tetapi kita masih membiarkannya sampai tak terbatas? $\Theta$ $i$ $n$ $n \to \infty$ $\Theta(n)$ $n$ $i$

Menerjemahkan (untuk batas atas, batas bawah bekerja dengan cara yang sama), kita dapatkan $(1)$

$\qquad \displaystyle \exists f_1, \dots, f_n \in \Theta(f).\ S_n \leq \sum_{i=1}^n f_i(i)$

Sekarang jelas bahwa sum- dan parameter- yang dipisahkan: kita dapat dengan mudah menentukan sehingga mereka menggunakan sebagai konstan. Dalam contoh dari pertanyaan, kita dapat mendefinisikan dan memiliki $i$ $i$ $f_i$ $i$ $f_i(j) = i \cdot \frac{1}{j} \in \Theta(1/j)$

$\qquad \displaystyle \sum_{i=0}^n f_i(i) "=" \sum_{i=0}^n \Theta(1/j) = \sum_{i=0}^n \Theta(1/i)$

tetapi jumlah aslinya jelas tidak mengevaluasi sesuatu di . Sekarang menukar untuk - yang hanya mengubah nama - di mungkin terasa aneh karena tidak terlepas dari resp. jumlah, tetapi jika kita keberatan dengan itu sekarang , kita seharusnya tidak pernah menggunakan di dalam di tempat pertama (karena yang memegang keanehan yang sama). $\Theta(H_n) = \Theta(\log n)$ $j$ $i$ $\Theta$ $i$ $n$ $i$ $\Theta$

Perhatikan bahwa kami bahkan tidak mengeksploitasi bahwa juga bergantung pada . $f_i$ $n$

Untuk menyimpulkan, identitas yang diusulkan adalah palsu. Tentu saja kita dapat menyepakati konvensi tentang cara membaca jumlah seperti singkatan dari perhitungan yang ketat. Namun, konvensi semacam itu tidak akan sesuai dengan definisi istilah-istilah Landau (bersama-sama dengan pelecehan normal terhadap mereka), tidak mungkin untuk dipahami dengan benar tanpa konteks dan menyesatkan (untuk pemula) setidaknya - tetapi itu pada akhirnya adalah masalah selera (dan kekejaman) ?).

Terpikir olehku bahwa kami juga dapat menulis dengan tepat apa yang kami maksud dan masih memanfaatkan kenyamanan istilah-istilah Landau. Kita tahu bahwa semua puncak datang dari satu fungsi umum, menyiratkan bahwa batas asimptotik menggunakan konstanta yang sama. Ini hilang ketika kita memasukkan ke dalam jumlah. Jadi mari kita tidak meletakkannya di sana dan menulis $\Theta$

$\qquad \displaystyle \sum_{i=1}^n \frac{2i - 1}{i(i+1)} \in \Theta\left(\sum_{i=1}^n \frac{1}{i}\right) = \Theta(H_n)$

sebagai gantinya. Menempatkan luar hasil penjumlahan $\Theta$

pernyataan matematis yang benar dan
istilah sederhana di dalam bisa kita tangani dengan mudah (yang kita inginkan di sini, kan?). $\Theta$

Jadi bagi saya sepertinya ini adalah cara yang benar dan berguna untuk menuliskan masalah ini, dan karena itu harus lebih disukai daripada menggunakan simbol Landau di dalam jumlah ketika kita berarti mereka di luar itu.

Raphael
sumber

Pertimbangkan . Saya dapat mendefinisikan (menggunakan sebagai konstanta), oleh karena itu dengan alasan Anda, bukan? Tetapi jumlah ini adalah .

\sum_{i}^{n} i

$\sum_i^n i$

f_{i} (n) = i

$f_i(n)=i$

i

$i$

\sum_{i}^{n} i = \sum_{i}^{n} O (1) = O (n)

$\sum_i^n i = \sum_i^n O(1) = O(n)$

O (n^{2})

$O(n^2)$

Xodarap

@Xodarap: Dengan alasan saya, runtuh jumlahnya seperti ini tidak bekerja, karena kopling dalam s (yang tidak digabungkan dengan atau ) untuk tidak mengubah makna.

Θ

$\Theta$

i

$i$

n

$n$

n

$n$

Raphael

Saya tidak mengaitkannya dengan , saya hanya menggunakan fakta bahwa . (Dan saya kira juga fakta bahwa .)

n

$n$

\sum_{i}^{n} k = n k

$\sum_i^n k = nk$

n O (f) = O (n f)

$nO(f)=O(nf)$

Xodarap

@Xodarap: Tapi Anda tidak punya satu , tapi satu per musim panas. Jika fungsi dasar menggunakan (sebagai faktor konstan), Anda harus mengembangkannya, dan jumlah akhirnya menjadi benar. Jadi, jelas, dengan alasan saya aturan penjumlahan yang Anda usulkan tidak berfungsi saat Anda menulis.

f

$f$

f_{i}

$f_i$

f_{i}

$f_i$

i

$i$

Raphael

Jika saya memiliki urutan , masing-masing adalah (asalkan mereka tidak meningkat seiring seri berlangsung). Apakah Anda mengatakan bahwa menambahkan dari mereka akan menghasilkan jumlah ? Apa bedanya jika alih-alih menjadi konstanta, saya menggambarkannya sebagai fungsi konstan ?

5, 1, 3, 2, \dots

$5,1,3,2,\dots$

O (1)

$O(1)$

n

$n$

O (n)

$O(n)$

f_{1} (x) = 5, f_{2} (x) = 1, \dots

$f_1(x)=5,f_2(x)=1,\dots$

Xodarap

-1

Jika setiap adalah konstanta, maka ada beberapa sedemikian rupa sehingga . Jadi jelas Ide yang sama untuk sedikit Hai. $c_i$ $c_{max}$ $\forall c_i: c_i\leq c_{max}$

\sum c_{i} f (i) \leq \sum c_{m a x} f (i) = c_{m a x} \sum f (i) = O (\sum f (i))

$\sum c_i f(i) \leq \sum c_{max} f(i) = c_{max} \sum f(i) = O\left(\sum f(i)\right)$

Saya pikir masalahnya di sini adalah . Ini (karena tidak ada sehingga ), jadi jumlah keseluruhannya adalah . Dan setiap istilah adalah , artinya jumlah keseluruhannya adalah . Jadi tidak ada batasan ketat yang dapat ditemukan dari metode ini. $1/i\not=\Theta(1)$ $o(1/n)$ $\epsilon$ $\forall i: 1/i>\epsilon$ $no(1/n)=o(1)$ $O(1)$ $O(n)$

Saya pikir pertanyaan Anda adalah:

Apakah membatasi dengan melakukan sedikit dari setiap istilah dan besar dari setiap istilah kemudian dikalikan dengan dapat diterima? (Jawab: Ya) $\sum_i^n f(i)$ $n$
Apakah ada metode yang lebih baik? (Jawab: Bukan yang saya tahu.)

Semoga orang lain bisa menjawab # 2 dengan lebih jelas.

EDIT: Melihat kembali pertanyaan Anda, saya pikir Anda bertanya

$\sum_i^n \Theta(f(n)) = \Theta(nf(n))$ ?

Yang jawabannya adalah ya. Namun dalam hal ini, setiap istilah bukanlah apa pun, sehingga pendekatan itu berantakan. $\Theta$

EDIT 2: Anda mengatakan "pertimbangkan , maka tidak ada ". Benar-benar benar. Jika Anda mengatakan bahwa adalah fungsi non-konstan dari , maka, menurut definisi, non-konstan. $c_i=i$ $c_{max}$ $c_i$ $i$

Perhatikan bahwa jika Anda mendefinisikannya dengan cara ini, maka bukan , itu . Memang, jika Anda mendefinisikan "konstan" berarti "fungsi ", maka dua fungsi berbeda dengan "konstan"! $c_i i$ $\Theta(i)$ $\Theta(i^2)$ $i$ $i$

Mungkin ini adalah cara yang lebih mudah untuk memikirkannya: kita memiliki urutan . Apa istilah terkecil dalam urutan ini? Yah, itu akan tergantung pada . Jadi kita tidak bisa menganggap istilah itu konstan. $1,\frac{1}{2},\dots,\frac{1}{n}$ $n$

(Ilmuwan komputer sering lebih akrab dengan big-O, jadi mungkin lebih intuitif untuk bertanya apakah memiliki istilah terbesar yang konstan.) $1,\dots,n$

Untuk memberikan bukti Anda: biarkan menjadi nilai terkecil dari dalam rentang . Kemudian $f(i_{min})$ $f(i)$ $1,\dots,n$

\sum_{i}^{n} f (i) \geq \sum_{i}^{n} f (i_{m i n}) = n f (i_{m i n}) = n o (f (n))

$\sum_i^n f(i) \geq \sum_i^n f(i_{min}) = n f(i_{min}) = n o(f(n))$

Bukti analog dapat dibuat untuk batas atas.

Terakhir, Anda menulis bahwa dan sebagai bukti berikan bahwa . Ini sebenarnya adalah bukti-balik: jika "lebih besar" dari , maka itu tidak bisa "lebih kecil" dari , yang diperlukan untuk itu menjadi . Jadi tidak mungkin . $H_n = o(n)$ $H_n = \Theta(\log n)$ $H_n$ $n$ $\log n$ $\Theta(\log n)$ $o(n)$

Xodarap
sumber

1) "..kemudian ada beberapa sedemikian rupa sehingga ..." - tidak, tidak ada. Pertimbangkan dengan . 2) "Saya tidak berpikir " - 3) . Ini - Itu salah. Seperti , . 4) "(Jawab: Ya)" - selama saya tidak melihat bukti resmi dari fakta itu, saya tidak percaya. Selain itu, "mengalikan dengan " bukan yang terjadi dalam kasus yang dipamerkan.

c_{m a x}

$c_{max}$

(c_{i})_{i \in N}

$(c_i)_{i \in \mathbb{N}}$

c_{i} = i

$c_i = i$

H_{n} = o (n)

$H_n=o(n)$

H_{n} \in Θ (\ln n)

$H_n \in \Theta(\ln n)$

1 / i \neq Θ (1)

$1/i\not=\Theta(1)$

o (1 / n)

$o(1/n)$

1 / i \geq 1 / n

$1/i \geq 1/n$

1 / i \in Ω (1 / n)

$1/i \in \Omega(1/n)$

n

$n$

Raphael

Saya pikir kamu melewatkan intinya. Bukti Anda tidak berfungsi karena kami mungkin tidak memiliki sama di setiap musim, dan bahkan tidak sama untuk musim yang sama tetapi berbeda . Saya pikir saya berhasil melakukannya; Saya akan menulis jawaban segera.

f

$f$

n

$n$

Raphael

Saya masih tidak mengerti apa yang Anda katakan, jadi saya senang Anda menemukan

jawabannya