CoE KKU dsa

dsa:adt

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:40:09+00:00

3.1. Abstract Data Types (ADTs) Abstract data type (ADT) คือ เซต (set) ของออปเจ็กต์ (objects) ที่ประกอบด้วยเซตของการดำเนินการ (operations) Abstract data types เป็น mathematical abstractions; กล่าวคือในนิยามของ ADT ไม่ได้แสดงให้เห็นถึงวิธีการทำงานของ operations ต่าง ๆ ว่าการทำงานของมันเป็นอย่างไร ออปเจ็กต์ เช่น lists, sets, และ graphs, รวมทั้ง operations ของมันถูกมองเป็น abstract data types ได้เช่นเดียวกับ integers, reals, และ booleans ที่มี operations ต่าง ๆ ผูกคิดอยู่กับมัน สำหรับ ADT ที่เ…

dsa:analysis0

Anonymous (anonymous@undisclosed.example.com) — 2021-09-07T10:39:39+00:00

2. Algorithm Analysis ในบทนี้กล่าวถึงเนื้อหาที่เกี่ยวข้องกับหัวข้อต่อไปนี้ การประเมินเวลาที่โปรแกรมใช้ในการทำงาน การลดเวลาที่โปรแกรมต้องใช้ (เรียกว่า running time) Algorithm คือ set ของ instructions (อย่างง่าย) ที่ต้องใช้ดำเนินการเพื่อแก้ปัญหา…

dsa:analysis1

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:04:02+00:00

2.1. พื้นฐานคณิตศาสตร์ เราจะใช้นิยามคณิตศาสตร์ต่อไปนี้ในการวิเคราะห์อัลกอริทึมตลอดบทเรียนของเรา$T(n) = O(f(n))$$c$$n_0$$T(n) \leq cf(n)$$n > n_0$$T(n)= \Omega(f(n))$$c$$n_0$$T(n) \geq cf(n)$$n > n_0$$T(n)= \Theta(f(n))$$T(n) = O(f(n))$$T(n)= \Omega(f(n))$$T(n) = o(p(n))$$c$$n_0$$T(n) < cp(n)$$n > n_0$$T(n) = o(p(n))$$T(n) = O(p(n))$$T(n) ≠ \Theta(p(n))$$T(n) = ω(p(n))$$c$$n_0$$T(n) > cp(n)$$n > n_0$$T(n) = ω(p(n))$$T(n) = Ω(p(n))$$T(n) ≠ \Theta(p(n))$$T(n) = O(f(n))$$T(n) = \Omega(f(n))$$T(n) =…

dsa:analysis2

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:39:36+00:00

2.3. สิ่งที่ต้องวิเคราะห์ การใช้ทรัพยากรที่สำคัญที่สุดที่ต้องทำการวิเคราะห์ คือ running time มีปัจจัยหลายอย่างที่มีผลต่อ running time ของโปรแกรม ปัจจัยบางอย่างเช่น compiler และ computer ที่ใช้ก็ไม่เกี่ยวข้องกับโมเดลที่เราได้กล่าวไปแล้ว ดังนั้นจะไม่กล่าวถึงในที่นี้ ปัจจัยอื่นที่สำคัญ คือ ตัวอัลกอริทึมที่ใช้เองและอินพุตที่ใช้ในอัลกอริทึมนั้น ๆ และโดยทั่วไปแล้วขนาดของอินพุตเป็นสิ่งที่เราจะให้ความสนใจเป็นเรื่องหลัก$T_{avg}(n)$$T_{worst}(n)$$T_{avg}(n) < T_{worst}(n)$$a_1, a_2, . . . , a_n$$∑_{k=i}…

dsa:basic_math

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T11:37:20+00:00

1.2 ทบทวนคณิตศาสตร์ที่จำเป็น 1.2.1 Exponents $$ 𝑋^𝐴 * 𝑋^𝐵 = 𝑋^{(𝐴+𝐵)} $$ $$ 𝑋^𝐴/𝑋^𝐵 = 𝑋^{(𝐴−𝐵)} $$ $$ (𝑋^𝐴)^𝐵 = 𝑋^{𝐴𝐵} $$ $$ 𝑋^𝑁 + 𝑋^𝑁 = 2𝑋^𝑁 ≠ 𝑋^{2𝑁} $$ $$ 2^𝑁+2^𝑁 = 2^{(𝑁+1)} $$ 1.2.2 Logarithms ส่วนใหญ่ที่ใช้เป็น logarithms ฐาน 2 นิยาม: $𝑋^𝐴 = 𝐵$ 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓 $𝑙𝑜𝑔_𝑥 𝐵 = 𝐴$$$ log⁡(𝐴𝐵)=log⁡𝐴+log⁡𝐵 $$$$ log⁡(𝐴/𝐵)=log⁡𝐴−log⁡𝐵 $$$$ log⁡(𝐴^𝐵)=B log⁡𝐴 $$$log⁡ 𝑋 < X$$X > 0$$$ log_𝐴⁡𝐵 = \frac{log_𝑐⁡𝐵}{log_𝑐⁡𝐴} ; A, B, C > 0, A≠1 $$$X = log_c B, Y = log_c A, และ Z = log_A B.$$C^X = B, C^Y =…

dsa:dsanalysis

Anonymous (anonymous@undisclosed.example.com) — 2021-09-10T21:13:50+00:00

8.6. Worst Case สำหรับ Union-by-Rank และ Path Compression เวลาสำหรับกรณี worst case คือ $\Theta(M A(M, N))$ (โดย M ≥ N), เมื่อ $A(M, N)$ คือ functional inverse ของ Ackerman's function, ซึ่งมีนิยามดังนี้ $$A(1, j) = 2j for j ≥ 1$$$$A(i, 1) = A(i - 1, 2) for i ≥ 2$$$$A(i, j) = A(i - 1, A(i, j - 1)) for i, j ≥ 2$$$$\alpha(M, N) = min{ i ≥ 1 : A( i, ⌊M / N⌋ ) > log\ N } $$$\alpha(M, N) ≤ 4$$F(N) = A(2, N)$$log^*\ N$$log^* 65536 = 4$$log\ log\ log\ log\ 65536 = 1$$log^* 2^{65536} = 5$$\alpha(M, …

dsa:dsapp

Anonymous (anonymous@undisclosed.example.com) — 2021-09-10T15:51:48+00:00

8.7 ตัวอย่างการประยุกต์ ตัวอย่างของการใช้โครงสร้างข้อมูล union/find ที่เสนอนี้เป็นการใช้เพื่อการสร้าง mazes ดังแสดงในรูปที่ 8.19 จุดเริ่มต้นของรูปอยู่ที่ด้านบนและจุดสิ้นสุดอยู่ที่ตำแหน่งด้านล่างรูป เราสามารถมอง maze ได้ว่าเป็นรูปสี่เหลี่ยมที่ประกอบด้วยเซลล์สี่เหลี่ยมขนาดเล็กจำนวนหนึ่งขนาด m-by-n เซลล์ ซึ่งเป็นเซลล์ที่เชื่อมต่อทางเข้ากับทางออด และแต่ละเซลล์แยกจากเซลล์ที่อยู่ติดกันด้วยผนัง $2N$$4N$$O(N\ log*\ N)$…

dsa:dsbasic

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:28:18+00:00

8.3. Basic Data Structure การทำงาน find ไม่ต้องการคำตอบที่เป็นการระบุถึงชื่อใด ๆ หากแต่เพียงต้องการคำตอบว่าการ find สมาชิกทั้งสองตัวนั้นจะให้คำตอบที่เหมือนกันถ้า (if and only if) มันอยู่ใน set เดียวกัน แนวคิดหนึ่งคือ การใช้โครงสร้างทรี (tree) สำหรับแต่ละเซต เนื่องจากสมาชิกแต่ละตัวนั้นมีรากเดียวกัน ดังนั้นเราจึงใช้ชื่อของรากเป็นชื่อของเซตดังกล่าวได้ เราจะแทนเซตหนึ่งเซตด้วยทรีหนึ่งทรี ตอนเริ่มต้นแต่ละเซตประกอบด้วยสมาชิกหนึ่งตัว (กลุ่มของทรีเรียกว่า forest) ทรีที่เราใช้นี้ไม่จำเป็นต้องเป็น binary …

dsa:dsdeq

Anonymous (anonymous@undisclosed.example.com) — 2021-09-10T16:00:24+00:00

8.2. The Dynamic Equivalence Problem ในกรณีที่เรามี equivalence relation ~, แล้วจะมีปัญหาพื้นฐานที่ต้องตอบเสมอ คือ สำหรับ a และ b ใด ๆ แล้ว a ~ b หรือไม่ ถ้าความสัมพันธ์นี้ได้รับการจัดเก็บในรูปของอะเรย์ 2 มิติของค่า Boolean แล้วเราก็จะได้คำตอบทันที่ด้วยเวลาที่เป็นค่าคงที่ แต่ปกติแล้วความสัมพันธ์ระหว่างมันไม่ได้มีแสดงตัวตนของมันออกมาอย่างชัดเจน$O(1)$$\Theta(N)$$\Theta(N^2)$$\Omega(N^2)$$O(1)$$\Theta(N^2)$$O(N\ log\ N)$$log\ N$$O(M + N\ log\ N)$$O(M + N)$…

dsa:dseq

Anonymous (anonymous@undisclosed.example.com) — 2021-09-10T15:55:20+00:00

8.1. Equivalence Relations นิยามของ relation $R$ ในเซต $S$ กำหนดได้ถ้าทุก ๆ คู่ของสมาชิก $(a, b), a, b ∈ S $, แล้ว $a\ R\ b$ เป็นจริงหรือเท็จก็ได้ ถ้า $a\ R\ b$$a\ R\ a$$a ∈ S$$a\ R\ b$$b\ R\ a.$$a\ R\ b$$b\ R\ c$$a\ R\ c.$

dsa:dsintro

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T13:24:22+00:00

8. THE DISJOINT SET ADT ในบทนี้กล่าวถึงโครงสร้างข้อมูลที่ใช้ในการแก้ปัญหาที่เรียกว่า ปัญหาการสมมูล (equivalence problem) เป็นโครงสร้างข้อมูลที่ง่ายในการสร้าง โปรแกรมที่เขียนสำหรับโครงสร้างนี้มีขนาดเล็ก สามารถใช้โครงสร้างแบบอะเรย์ได้ และสามารถทำงานได้อย่างรวดเร็วใช้เวลาเฉลี่ยเป็นเวลาคงที่ต่อการทำงานหนึ่ง โครงสร้างข้อมูลชนิดนี้เป็นที่สนใจในทางทฤษฏีเนื่องจากการวิเคราะห์ทำได้ยากมากรูปแบบฟังก์ชันของกรณี worst case ก็แตกต่างจากที่ได้ที่ได้กล่าวมาแล้ว เนื้อหาที่จะกล่าวเกี่ยวกับ Disjoint set ADT:…

dsa:dspath

Anonymous (anonymous@undisclosed.example.com) — 2021-09-10T21:07:22+00:00

8.5. Path Compression การทำงานของ union/find algorithm ที่ได้กล่าวมาแล้วในกรณีโดยทั่วไปเป็นที่ยอมรับได้เนื่องจากไม่ซับซ้อนและใช้เวลาเฉลี่ยเป็น linear สำหรับลำดับการทำงาน M คำสั่งต่อเนื่องกัน อย่างไรก็ตามมันอาจเกิดกรณี worst case ที่มี running time เป็น O(M log N) ได้ง่ายเป็นเรื่องปกติ เช่น ถ้าเราจัดให้เซตทั้งหมดเข้าไปอยู่ในคิว ๆ หนึ่งและให้ดำเนินการซ้ำ ๆ ด้วยการ dequeue สองเซตแรกและตามด้วย enqueue ผลที่ได้ของการ union เช่นนี้ก็จะเกิดกรณี worst-case ขึ้น ถ้าหากว่ามีการทำงาน find เป็นจำนวนครั้งที…

dsa:dsunion

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:32:17+00:00

8.4. Smart Union Algorithms การ unions ดังที่กล่าวมาข้างบนไม่มีข้อกำหนดใดกำกับเพียงแต่ใช้ทรีตัวที่สองไปเป็นทรีย่อยของทรีตัวแรก การปรับปรุงอย่างง่ายให้การทำงานดีขึ้นคือกำหนดให้ทรีที่มีขนาดเล็กกว่าไปเป็นทรีย่อยของทรีที่มีขนาดใหญ่กว่าเสมอ และเรียกวิธีนี้ว่า union-by-size $log\ N$$log\ N$$O(log\ N)$$M$$O(M\ log\ N)$$O(M)$$O(log\ N)$…

dsa:gdef

Anonymous (anonymous@undisclosed.example.com) — 2021-10-06T08:48:06+00:00

9.1 นิยาม Graph $G = (V, E)$ ประกอบด้วยเซตของ vertices V, และเซตของ edges E แต่ละ edge คือคู่ $(v,w)$ เมื่อ $v,w ∈ V$ บางครั้งก็เรียก Edges ว่า arcs $w$$v$$(v,w) ∈ E$$(v,w)$$(w,v)$$w$$v$$v$$w$$w_1, w_2, w_3, . . . , w_N$$(w_i, w_{i+1}) ∈ E$$(v,v)$$v$$v$$w_1 = w_N$$\Theta(|V|^2)$$|E| = \Theta(|V|^2)$$|E| ≈ 4 |V|$$O(|E| + |V|)$

dsa:gdfs

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T10:34:14+00:00

9.6 การประยุกต์ใช้วิธีค้นหา Depth-First Search Depth-first search เป็นลักษณะทั่วไปของ preorder traversal เริ่มต้นด้วยการประมวลผลที่ vertex v ใด ๆ แล้วจากนั้นจะท่องไปในทุก vertices ที่เป็น adjacent กับ v ในแบบ recursive $O(|E|)$$|E| = \Theta(|V|)$$O(|E| + |V|)$$O(|E| +|V|)$$O(|E|)$$O(|E| + |V|)$…

dsa:gintro

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T09:34:40+00:00

9. Graph Algorithms ในบทนี้จะกล่าวถึงปัญหาทั่วไปของทฤษฎีกราฟ โดยจะกล่าวถึงหัวข้อต่อไปนี้ * กล่าวถึงปัญหาในชีวิตประจำวันที่สามารถเปลี่ยนมาแก้ปัญหานั้น ๆ ได้ด้วยการใช้ทฤษฎีกราฟ

dsa:gmst

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T10:19:14+00:00

9.5. Minimum Spanning Tree ปัญหาที่จะกล่าวถึงต่อไป คือการหา minimum spanning tree ใน undirected graph กล่าวอย่างไม่เป็นทางการแล้ว minimum spanning tree ของ undirected graph G ก็คือ tree ที่สร้างจาก edge ของกราฟที่เชื่อมต่อ vertices ทั้งหมดของ G โดยที่มี cost รวมต่ำสุด จะมี minimum spanning tree จากกราฟได้ก็ต่อเมื่อกราฟ G นั้นต้องเป็นกราฟแบบ connected เท่านั้น ถึงแม้ว่าอัลกอริทึมที่ดีจะต้องสามารถรายงานได้ในกรณีที่กราฟไม่เป็นแบบ connected ในระหว่างการทำงานของมันก็ตาม ในที่นี้เราให้ความสนใจเฉพาะที…

dsa:gnetf

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T09:51:05+00:00

9.4. Network Flow Problems ถ้ากำหนดให้มี directed graph $G = (V, E)$ ที่มี edge capacities $c_{v,w}$ โดยที่ขีดจำกัดของ edge นี้อาจหมายถึงจำนวนปริมาณน้ำที่สามารถจะไหลผ่านท่อได้เต็มที่หรืออาจจะหมายถึงจำนวนยานพาหนะที่ถนนระหว่างจุดตัด 2 จุดสามารถรองรับได้เต็มที่ก็ได้ ถ้าเรามีสอง vertices ที่ vertex แรกคือ s เรียกว่า source และ vertex ที่สองคือ t เรียกว่า sink และถ้าให้ใน edge (v, w) ใด ๆ จะมีของไหลผ่านได้สูงสุดเป็นจำนวน $c_{v,w}$$G$$G_f$$G_r$$G_f$$G_f$$G_f$$G_r$$G_r$$G_r$$G_f$$G_r$$G_r$$G, G_f, G_r…

dsa:gstp

Anonymous (anonymous@undisclosed.example.com) — 2021-10-06T09:27:32+00:00

9.3. Shortest-Path Algorithms ในหัวข้อนี้จะกล่าวถึงปัญหาที่เรียกว่า shortest-path problems อินพุตเป็น weighted graph: กล่าวคือ edge $(v_i, v_j)$ มีค่าใช้จ่าย (cost) $c_{i,j}$$v_1,v_2, ... v_n$$∑_{i=1}^{N-1}c_{i,i+1}$$G = (V, E)$$G$$O(|E| + |V|)$$O(|E|\ log\ |V|)$$O(|E|\ ×\ |V|)$$O(|V|^2)$$O(|V|)$$O(|V|^2)$$O(|E|)$$O(|E| + |V|^2) = O(|V|^2)$$|E| = \Theta(|V|^2)$$|E| = \Theta(|V|)$$O(log\ |V|)$$O(|E|\ log\ |V| + |V|\ log\ |V|) = O(|E|\ log\ |V|)$$|E|$$|E| ≤ |V|^2$$log |E| ≤ 2\ log |V|$$O(|E|\ log…

dsa:gtopo

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T08:24:34+00:00

9.2. Topological Sort topological sort คือลำดับของ vertices ใน directed acyclic graph ที่ถ้ามี path หนึ่งจาก $v_i$ ไปยัง $v_j$, แล้ว $v_j$ มีลำดับที่ตามหลัง $v_i$$v1, v2, v5, v4, v3, v7, v6$$v1, v2, v5, v4, v7, v3, v6$$O(|V|)$$|V|$$O(|V|^2)$$O(|E| + |V|)$

dsa:hashing

Anonymous (anonymous@undisclosed.example.com) — 2021-09-07T10:40:22+00:00

5. Hashing ในบทที่ผ่านเราได้กล่าวถึง search tree ADT ซึ่งสนับสนุนการดำเนินงานหลายอย่างกับเซตของสมาชิกได้ ในบทนี้จะกล่าวถึง Hash table ADT ที่สนับสนุนการดำเนินงานงานเพียงบางอย่างที่มีอยู่ใน binary search tree เท่านั้น…

dsa:hclose

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:46:07+00:00

5.4 Open Addressing Separate chaining มีข้อเสียเปรียบที่การต้องใช้ลิงค์ลิสต์ ทำให้การทำงานช้าลงไปบ้างเนื่องจากต้องใช้เวลาในการ allocate เซลล์ใหม่, และโดยเฉพาะอย่างยิ่งเราต้องใช้โครงสร้างข้อมูลโครงสร้างที่สอง การใช้ Open addressing เป็นทางเลือกการแก้ปัญหาการชนแทนการใช้ลิงค์ลิสต์ โดยเมื่อเกิดการชนขึ้นก็จะทำการหาตำแหน่งเซลล์ว่างใหม่จนกว่าจะพบเซลล์ว่าง กล่าวคือ จะตรวจสอบเซลล์ $h_0(x), h_1(x), h_2(x), ...$$h_i(x) = (hash(x) + f(i))\ mod\ TableSize$$f(0) = 0$$f$$\lambda = 0.5$$f(i) = i$$f(i) = i$$\fr…

dsa:hextend

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:46:49+00:00

5.7 Extendible Hashing หัวข้อสุดท้ายที่จะกล่าวถึงในบทนี้คือกรณีที่จำนวนข้อมูลมีปริมาณมากเกินกว่าที่จะบรรจุลงในหน่วยความหลักได้ทั้งหมด ดังที่ได้กล่าวไปแล้วในบทที่ 4 ว่าสิ่งที่จะต้องให้ความสนใจในกรณีเช่นนี้ คือจำนวนครั้งในการเข้าถึงแผ่นจานแม่เหล็กที่เราต้องการอ่านเขียนหรือค้นหาข้อมูล$O(N)$$O(log_{M/2}⁡N)$…

dsa:hfunction

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:45:42+00:00

5.2 Hash Function ถ้าค่า key เป็นเลขจำนวนเต็ม เพียงใช้ key mod TableSize ก็เป็นการเพียงพอ, เว้นเสียแต่บังเอิญว่าค่า key มีคุณสมบัติที่ไม่พึงประสงค์บางประการที่อาจจะต้องพิจารณาการเลือก hash function ด้วยความระมัดระวังมากขึ้น เช่น ถ้าค่า key ทั้งหมดเป็นค่าที่ลงท้ายด้วยศูนย์และขนาดของตารางคือ 10 การใช้ฟังก์ชันนี้ก็เป็นสิ่งที่ต้องหลีกเลี่ยง เพื่อหลีกเลี่ยงปัญหาดังกล่าวนี้ ปกติแล้วควรเลือกให้ขนาดตารางเป็น prime number ซึ่งถ้ากรณีที่ key เป็นเลขจำนวนเต็มแบบสุ่ม (random integers) นอกจากการใช้ฟังก์ชันน…

dsa:hgeneral

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:44:55+00:00

5.1 แนวคิด กล่าวโดยทั่วไปแล้ว โครงสร้างข้อมูลของ hash table ก็คือ อะเรย์ที่มีขนาดคงที่และมีหน่วยข้อมูล เรียกว่า keys บรรจุอยู่ เช่น หน่วยข้อมูลอาจจะประกอบด้วยสตริง (ซึ่งถูกกำหนดให้ใช้เป็น key) และฟิลด์อื่น ๆ (เช่น ชื่อลูกจ้างที่เป็นส่วนประกอบหนึ่งของโครงสร้างข้อมูลของลูกจ้าง)…

dsa:hopen

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:04:56+00:00

5.3 Separate Chaining (open hashing) การแก้ปัญหาการชนด้วยวิธี separate chaining (open hashing) ใช้ลิสต์ (list) เพื่อเก็บรายการของค่าที่ hash แล้วได้ค่าเท่ากัน โดยเราจะใช้ลิสต์แบบที่มี header เพื่อความสะดวกในการใช้งาน เพื่อความสะดวกในการอธิบาย ในที่นี้เราจะสมมุติให้ค่า key มีค่าเป็นเลข perfect squares จำนวน10 ตัว และใช้ hashing function อย่างง่ายคือ $hash(x) = x mod 10$$\lambda$$\lambda = 1.0$$\lambda$$\lambda$$\lambda + (\lambda/2)$$(N – 1) M = \lambda - 1/M$$\lambda$$\lambda/2$$1 + (\lambda/…

dsa:hother

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:46:35+00:00

5.6 Hash Tables with Worst-Case O(1) Access 5.6.1 Perfect Hashing Suppose, for purposes of simplification, that all N items are known in advance. If a separatechaining implementation could guarantee that each list had at most a constant number of items, we would be done. We know that as we make more lists, the lists will on average be shorter, so theoretically if we have enough lists, then with a reasonably high probability we might expect to have no collisions at all!$M$$M$$M = (N^2)$$M = N^…

dsa:hrehash

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T08:36:19+00:00

5.5 Rehashing กล่าวสำหรับ Open addressing ที่ใช้ quadratic probe แล้ว เมื่อตารางถูกใช้งานจนใกล้จะเต็ม running time ของการดำเนินการต่าง ๆ ก็จะมากขึ้นและการบรรจุค่าใหม่ก็อาจจะทำไม่ได้เลย สิ่งนี้ยังเกิดขึ้นกับกรณีที่มีการลบและบรรจุร่วมกันจำนวนมาก ๆ ด้วย ทางแก้หนึ่งก็คือ สร้างตารางขึ้นใหม่ให้มีขนาดเป็นสองเท่า (ร่วมกับการใช้ hash function ใหม่) แล้วย้ายข้อมูลในตารางเดิมไปลงในตารางใหม่ด้วยการคำนวณค่า hash value ใหม่สำหรับแต่ละค่าที่อ่านจากตารางแฮชเดิม (ที่เป็น non-deleted)$h(x) = x\ mod\ 7$$h(x) = x\…

dsa:intro

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:35:09+00:00

1. บทนำ ในบทนี้กล่าวถึงเนื้อหาที่เกี่ยวข้องกับหัวข้อต่อไปนี้ * ความสำคัญของโปรแกรมที่ใช้งานข้อมูลอินพุตจำนวนมาก

dsa:intro1

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:37:56+00:00

1.1 ว่าด้วยเนื้อหาวิชา การเขียนโปรแกรมที่สามารถใช้งานได้ยังไม่เป็นการเพียงพอ ถ้าหากว่าต้องนำโปรแกรมดังกล่าวไปใช้งานกับข้อมูลจำนวนมาก ๆ แล้ว ประเด็นเรื่องเวลาที่ต้องใช้ในการทำงานของโปรแกรมก็จะเป็นสิ่งที่ต้องนำมาพิจารณา ดังนั้น การเรียนรู้การประเมิน running time ของโปรแกรมที่ใช้แก้ปัญหาสำหรับอินพุตขนาดใหญ่จึงมีความสำคัญ และที่สำคัญยิ่งกว่านั้น คือ เราสามารถเปรียบเทียบ running times ของโปรแกรมสองโปรแกรมโดยที่ไม่ต้องลงมือเขียนโปรแกรมจริงขึ้นมาก่อน นอกจากนั้นการประเมิน running time ยังทำให้เราสามาร…

dsa:list

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T10:42:40+00:00

3.2. The List ADT รูปแบบทั่วไปของ list คือ $a_1, a_2, a_3, ... , a_n$ และกล่าวว่ามันมีขนาดเป็น $n$ และเรียก list ที่มีขนาดเป็น 0 ว่า empty list สำหรับ list ใด ๆ ยกเว้น empty list, ค่า $a_{i+1}$$a_i\ (i < n)$$a_{i-1}$$a_i\ (i > 1)$$a_1$$a_n$$a_1$$a_n$$a_i$$i$$O(n)$$O(i)$$A_1,A_2,⋯,A_5$$O(n)$$O(n)$$O(1)$$f(x)=∑_{i=0}^n a_i x^i$$a_i$$P_1 (x)=10x^{1000}+5x^{14}+1$$P_2 (x)=3x^{1990}+2x^{1492}+11x+5$…

dsa:lsq

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T13:26:38+00:00

3. List, Stack and Queue ในบทนี้กล่าวถึงโครงสร้างข้อมูลที่เป็นโครงสร้างพื้นฐานอย่างง่ายที่สุด ความจริงแล้วโปรแกรมที่สำคัญ ๆ ต่าง ๆ ล้วนแต่ต้องใช้โครงสร้างพื้นฐานนี้อย่างใดอย่างหนึ่งเสมอ โดยเฉพาะอย่างยิ่ง stack จะถูกใช้งานในโปรแกรมโดยปริยายอยู่แล้ว โดยในบทนี้จะได้กล่าวถึงเนื้อหาที่ประกอบด้วย…

dsa:model

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:38:41+00:00

2.2. โมเดล (Model) โมเดลของการทำงานของอัลกอริทึมที่จะใช้เพื่อการวิเคราะห์อัลกอริทึมมีดังนี้ *

dsa:np

Anonymous (anonymous@undisclosed.example.com) — 2021-09-09T10:35:26+00:00

9.7 Introduction to NP-Completeness In this chapter, we have seen solutions to a wide variety of graph theory problems. All these problems have polynomial running times, and with the exception of the network flow problem, the running time is either linear or only slightly more than linear (O(|E| log |E|)). We have also mentioned, in passing, that for some problems certain variations seem harder than the original.

dsa:pqapp

Anonymous (anonymous@undisclosed.example.com) — 2021-09-17T10:19:46+00:00

6.4 การประยุกต์ใช้ Priority Queue มีการประยุกต์ใช้ priority queue ใน graph algorithms ได้อย่างมีประสิทธิภาพซึ่งจะได้กล่าวถึงในบทที่ 9 ในหัวข้อนี้จะแสดงตัวอย่างการใช้ priority queue ช่วยหาคำตอบของปัญหาการเลือก$O(N^2)$$O(N• k)$$O(k^2)$$(N – k) • k$$O(k^2) + O((N - k)k) = O(N• k)$$k = N/2$$O(N^2)$$O(N)$$O(log\ N)$$O(N + k\ log\ N)$$k = O(N/log\ N)$$O(N)$$O(k\ log\ N)$$k = N/2$$\Theta(N\ log\ N)$$O(N\ log\ N)$$S_k$$S_k$$S_k$$O(k)$$O(log\ k)$$S_k$$O(k + (N – k )\ log\ k ) = O(N\ log\ k )$…

dsa:pqbiheap

Anonymous (anonymous@undisclosed.example.com) — 2021-09-13T09:33:59+00:00

6.3 Binary Heap โครงสร้างข้อมูลที่เราใช้สำหรับ priority queue คือ binary heaps และเรียกสั้น ๆ ว่า heaps ซึ่งเป็นวิธีทั่วไปที่นิยมใช้ โครงสร้าง heaps มีคุณสมบัติสองอย่างเช่นเดียวกับ binary search trees คือ คุณสมบัติทางโครงสร้าง (structure property) และ คุณสมบัติทางลำดับค่า (heap order property) และก็เช่นเดียวกับ AVL trees กล่าวคือ การดำเนินการกับ heap อาจจะทำลายคุณสมบัติอย่างใดอย่างหนึ่งของมัน ดังนั้น เมื่อมีการดำเนินการที่ว่านี้แล้วจะต้องทำการปรับปรุง heap ให้มีคุณสมบัติกลับคืนสู่สภาพของมัน$h$$…

dsa:pqbinomialq

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:53:42+00:00

6.8 Binomial Queues ถึงแม้ว่าทั้ง leftish และ skew heaps จะสนับสนุนการดำเนินงานการควบรวบ การบรรจุ และการลบ deleteMin ที่มีประสิทธิภาพด้วยเวลาทำงานเป็น $O(log\ N)$$O(log\ N)$$B_k$$B_{k-1}$$B_{k-1}$$B_0, B_1, B_2, B_3$$B_4$$B_k$$B_0, B_1, . . ., B_k-1$$2^k$$k\choose d$$\frac{k!}{(d!(k-d)!)}$$B_3, B_2, B_0$$B_3, B_2, B_0$$B_0, B_1, B_2, B_3,$$B_4$$O(log\ N)$$O(log\ N)$$O(log\ N)$$B_i$$B_1$$O(N)$$B_0$$B_1$$B_0, B_1, ... , B_{k-l}$$O(log\ N)$$O(log\ N)$$O(log\ N)$…

dsa:pqdheap

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:52:47+00:00

6.5 d-Heaps d-heap มีลักษณะเดียวกับ binary heap ยกเว้นโนดใน d-heap มีโนดลูกได้มากที่สุดจำนวน d โนด (นั่นคือ binary heap ก็คือ 2-heap นั่นเอง)$O(log_d\ N)$$O(d\ log_dN)$$O(log\ N)$$O(log\ N)$

dsa:pqleftisheap

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:53:11+00:00

6.6 Leftist Heaps เป็นเรื่องที่ยากมากที่จะออกแบบโครงสร้างข้อมูลที่สนับสนุนการทำงานการควบรวมได้อย่างมีประสิทธิภาพ (ที่ใช้เวลาการควบรวมเป็น $o(N)$$\Theta(N)$$2^r – 1$$2^r – 1$$2^r+1 – 1$$( (2^r – 1) + (2^r – 1 ) + 1 = 2^r+1 – 1 )$

dsa:pqlist

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:52:03+00:00

6.2 Simple Implementations มีหลายวิธีการที่จะสร้างโครงสร้าง priority queue เพื่อใช้งาน เราสามารถใช้โครงสร้างลิงค์ลิสต์ โดยให้การบรรจุเข้าที่ด้านหัว(front) ของลิสต์โดยมี running time เป็น $O(1)$$O(N)$$O(N)$$O(1)$$O(log\ N)$$O(log\ n)$

dsa:pqmodel

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:51:44+00:00

6.1. Model Priority queue เป็นโครงสร้างข้อมูลที่สนับสนุนการดำเนินการอย่างน้อย 2 อย่าง คือ การบรรจุค่า (insert) ซึ่งเป็นการบรรจุ ลักษณะเดียวกับ enqueue และการทำงาน deleteMin ซึ่งเป็นการค้นหาค่า ส่งกลับ และทำการลบค่า โดยเป็นค่าที่น้อยที่สุดภายในโครงสร้างนั้น ในลักษณะเดียวกับการทำงาน dequeue ในโครงสร้างคิว โดย ให้ความหมายว่า ค่าที่น้อยที่สุดนี้ มีความสำคัญสูงสุด จึงถูกนำออกไปทำงานก่อน (แซงคิวตามความสำคัญ) ซึ่งต่างจาก โครงสร้างคิวธรรมดาที่ ข้อมูล เข้ามาก่อน จะออกไปก่อน (ดูรูปที่ 6.1)…

dsa:pqskewheap

Anonymous (anonymous@undisclosed.example.com) — 2021-09-17T11:06:21+00:00

6.7 Skew Heaps Skew heaps เป็น binary trees ที่มีข้อกำหนดคุณสมบัติ heap order แต่ไม่มีข้อกำหนดคุณสมบัติทางโครงสร้าง Skew heaps ไม่มีสารสนเทศที่เกี่ยวกับ null path length ของโนด เส้นทางขวาของโนด (right path) ของ skew heap อาจจะยาวแค่ไหนก็ได้ ดังนั้น จึงอาจจะมี running time กรณี worst-case ของการดำเนินการใด ๆ เป็น $O(N)$$M$$O(M\ log\ N)$$O(log\ N)$…

dsa:priorityq

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T13:27:31+00:00

6. Priority Queues Priority queue เป็น queue แบบหนึ่งที่มีคุณสมบัติพิเศษบางอย่างเพิ่มเติมขึ้นจาก queue ธรรมดาที่ได้เคยกล่าวมาแล้วในบทก่อนหน้านี้ ในบทนี้จะกล่าวถึง

dsa:queue

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:41:06+00:00

3.4. The Queue ADT คิว (queue) ก็เป็นลิสต์เช่นเดียวกันกับ stack เพียงแต่สำหรับคิวแล้ว การ insert เกิดขึ้นที่ด้านหนึ่งในขณะที่การ delete เกิดขึ้นที่อีกด้านหนึ่งของโครงสร้างคิว

dsa:sbound

Anonymous (anonymous@undisclosed.example.com) — 2021-09-26T22:20:23+00:00

7.8 ขอบเขตล่างทั่วไปของการจัดเรียง ในหัวข้อนี้จะพิสูจน์ให้เห็นว่าอัลกอริทึมใด ๆ ของการจัดเรียงที่ใช้เฉพาะการเปรียบเทียบค่าจะต้องใช้จำนวนครั้งการเปรียบเทียบค่าเป็น W (N log N) ครั้ง (ซึ่งก็คือเวลาที่ใช้นั่นเอง) ในกรณี worst-case ซึ่งการพิสูจน์นี้ยังสามารถขยายความเพื่อแสดงให้เห็นว่าแม้กรณีเฉลี่ยก็ต้องใช้จำนวนครั้งของของเทียบค่าเป็น W (N log N) สิ่งที่จะพิสูจน์ คือ อัลกอริทึมของการจัดเรียงค่าที่ใช้เฉพาะการเปรียบเทียบค่านั้น ต้องใช้จำนวนครั้งการในการเปรียบเทียบค่าเท่ากับ $log\ N!$$2^{d-1}$$2^d$$\…

dsa:sextenal

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:23:44+00:00

7.10 External Sorting อัลกอริทึมในการจัดเรียงที่กล่าวมาแล้วทั้งหมดนั้นต้องให้ข้อมูลทั้งหมดสามารถบรรจุอยู่ในหน่วยความจำหลัก ซึ่งเรียกว่า Internal sorting อย่างไรก็ตาม ในการประยุกต์ใช้งานทั่วไปนั้นมักมีปัญหาที่ไม่สามารถนำข้อมูลทั้งหมดมาบรรจุลงในหน่วยความจำหลักได้ในคราวเดียว ในหัวข้อนี้จะกล่าวถึงอัลกอริทึมการจัดเรียงที่เรียกว่า external sorting ซึ่งใช้จัดการกับข้อมูลอินพุตขนาดใหญ่มาก ๆ $x^{th}$$⌈N / 2^x * M⌉$\begin{align*} ⌈N / 2^x * M⌉ & = 1 \\ ⌈2^x⌉ & = ⌈N / M⌉ \\ x & …

dsa:sheap

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:16:12+00:00

7.5. Heapsort ในบทที่ 6 ได้กล่าวแล้วว่าเราอาจใช้ priority queues ในการจัดเรียงด้วยเวลา O(N log N) อัลกอริทึมที่ใช้พื้นฐานแนวคิดนี้ เรียกว่า heapsort และมี Big-Oh running time ดีกว่าอัลกอริทึมอื่น ๆ ที่กล่าวมาแล้ว อย่างไรก็ตาม ในทางปฏิบัติแล้วมันทำงานช้ากว่า shellsort ที่ใช้ลำดับการเพิ่มของ Sedwick…

dsa:sidebar

Anonymous (anonymous@undisclosed.example.com) — 2022-06-20T10:45:13+00:00

1. บทนำ * 1.1 ว่าด้วยเนื้อหาวิชา * 1.2 ทบทวนคณิตศาสตร์ที่จำเป็น 2. การวิเคราะห์ Algorithm * 2.1 พื้นฐานคณิตศาสตร์ * 2.2 โมเดล (Model) * 2.3 สิ่งที่ต้องวิเคราะห์ 3. List, Stack and Queue * 3.1 Abstract Data Type * 3.2 List * 3.3 Stack * 3.4 Queue 4. Tree * 4.1 Preliminaries * 4.2 Binary Tree * 4.3 The Search Tree ADT * 4.4 AVL Trees * 4.5 Splay Trees * 4.6 Tree Traversals (Revisited) * 4.7 B-Trees 5. Hashing * 5.1 แนวคิด * 5.2 Hash Function * …

dsa:sinsert

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:56:19+00:00

7.2. Insertion Sort 7.2.1. อัลกอริทึม Insertion Sort เป็นอัลกอริทึมอย่างง่ายอัลกอริทึมหนึ่งสำหรับการจัดเรียงค่า อัลกอริทึมมีการทำงานเป็นรอบที่ประกอบด้วยจำนวนรอบ N – 1 รอบ (passes) สำหรับจากรอบที่ p = 2 ถึง N ก็จะประกันได้ว่าสมาชิกที่อยู่ในตำแหน่ง 1 ถึง p จะถูกจัดอยู่ในลำดับที่ถูกต้องแล้ว การทำงานของ Insertion sort จะใช้ประโยชน์จากความจริงที่ว่าการทำงานในรอบที่ p นั้นสมาชิกในตำแหน่งที่ 1 ถึง p - 1 เป็นสมาชิกที่ถูกจัดเรียงเรียบร้อยแล้ว รูปที่ 7.1 แสดงตัวอย่างข้อมูลหลังการทำงานแต่ละรอบของ inse…

dsa:sintro

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:55:17+00:00

7.1 เบื้องต้น อัลกอริทึมที่จะกล่าวถึงจะมีการส่งผ่านอะเรย์ที่บรรจุสมาชิกอยู่ในทุกตำแน่งที่จะทำการจัดเรียง และประกอบด้วยจำนวนสมาชิก N ตัว object ที่จะทำการจัดเรียงนั้นเป็นชนิด (type) Comparable ซึ่งเป็น interface และต้อง implement ให้เหมาะสม และจะกำหนดให้ CompareTo method เพื่อใช้สำหรับจัดลำดับของอินพุต และเป็นการดำเนินการเดียวที่มีได้กับ input data นอกจาก assignments การจัดเรียงภายใต้เงื่อนไขที่กล่าวนี้เรียกว่า comparison-based sorting…

dsa:slinear

Anonymous (anonymous@undisclosed.example.com) — 2021-09-26T22:21:53+00:00

7.9. การจัดเรียงข้อมูลที่ใช้เวลาเป็น linear time ในบางกรณีที่เป็นกรณีพิเศษเราอาจทำการจัดเรียงข้อมูลได้ โดยใช้เวลาเป็น linear time ตัวอย่างอย่างง่ายได้แก่ bucket sort โดยจะต้องประกอบด้วยสารสนเทศเพิ่มเติมเพื่อให้มันทำงานได้ $A_1, A_2, ... , A_n$$A_i$$\left\lfloor k\bullet A_i/M\right\rfloor$$O(n)$$O(n^2)$$\left\lceil n/k\right\rceil$$k\bulletΟ(\lceil n/k \rceil ^2)$$O(n)$$Ο(n)+k∙Ο(\lceil n/k \rceil ^2)+Ο(n)$$k = O(n)$$n/2$$n/100$$\ k\bulletΟ( \lceil n/k \rceil ^2)$$O(n) O(1)$$O(n)$$A_i$$A_i$$A_i$…

dsa:slowerb

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:22:15+00:00

7.3 ขอบเขตล่าง (Lower Bound) ของอัลกอริทึมอย่างง่ายของการจัดเรียง คำว่า inversion ของตัวเลขในอะเรย์ คือ คู่อันดับ (ordered pair) (i, j) ใด ๆ ที่มีคุณสมบัติที่ i < j แต่มี a[i] > a[j] จากรูปที่ 7.1 มีอินพุตคือ 34, 8, 64, 51, 32, 21 มี inversions อยู่ทั้งสิ้น 9 ตัว คือ (34,8), (34,32), (34,21), (64,51), (64,32), (64,21), (51,32), (51,21) และ (32,21) ซึ่งจะเห็นได้ว่าตัวเลข 9 นี้จะเท่ากันกับจำนวนครั้งที่ต้องใช้ในการสลับค่าที่ใช้ใน insertion sort นั่นเอง ซึ่งจะเป็นจริงเช่นนี้เสมอ $\Omega(N^2)$$\Ome…

dsa:smerge

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:16:43+00:00

7.6 Mergesort Mergesort มี running time เป็น $O(N\ log\ N)$ กรณี worst-case และใช้จำนวนครั้งในการเทียบค่าที่เกือบจะ optimal และเป็นตัวอย่างที่ดีของอัลกอริทึมแบบ recursive$$ T(1) = 1$$$$ T(N) = 2T(N/2) + N $$$T(N) = O(N\ lg\ N)$

dsa:sort

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T13:27:51+00:00

7 การจัดเรียง (Sorting) ในบทนี้กล่าวถึงการจัดเรียงค่าในอะเรย์ เพื่อให้สามารถเข้าใจปัญหาได้ง่ายขึ้น เราจะสมมติให้สมาชิกในอะเรย์เป็นเลขจำนวนเต็มถึงกระนั้นโปรแกรมที่นำเสนอก็สามารถใช้ได้กับออปเจ็กต์อื่นทั่ว ๆ ไปได้ เกือบทั้งหมดของบทนี้เราจะให้จำนวนข้อมูลทั้งหมดที่กล่าวถึงสามารถบรรจุลงในหน่วยความจำหลักได้ทั้งหมด นั่นคือ การจัดเรียงสามารถทำได้ในหน่วยความจำ เรียกว่า internal sorting การจัดเรียงข้อมูลทั้งหมดที่ไม่สามารถทำได้ในหน่วยความจำแต่ต้องทำใน disk หรือ tape เรียกว่า external sorting จะกล่าวในตอนท…

dsa:squick

Anonymous (anonymous@undisclosed.example.com) — 2021-09-26T22:19:31+00:00

7.7. Quicksort quicksort เป็นอัลกอริทึมที่รับรู้กันว่าในทางปฏิบัติแล้วมันงานได้เร็วที่สุด มีค่า average running time เป็น $O(N\ log\ N)$$O(N^2)$$O(N\ log\ N)$$O(N^2)$$$T(N)= T(i)+ T(N - i - 1)+ cN \tag{7.1}$$$$ T(N) = T(N - 1) + cN,\ \ N > 1 \tag{7.2}$$$$ T(N) = O(N^2)$$$$ T(N) = 2T(N/2) + cN \tag{7.3}$$$$ T(N) = O(N lg N)$$$(1/N) ∑_{j=0}^{N-1} T(j) $$$T(N)=2/N [∑_{j=0}^{N-1}T(j)] + cN \tag{7.4}$$$$NT(N)=2[∑_{j=0}^{N-1}T(j)]+cN^2 \tag{7.5}$$$$(N - 1)T(N-1)=2[∑_{j=0}^{N-2}T(j)]+c(N-1)^2 \ta…

dsa:sshell

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T22:15:55+00:00

7.4 Shellsort Shellsort ตั้งตามชื่อของผู้คิดค้นการจัดเรียงแบบนี้ คือ Donald Shell (ในปี 1959) และเป็นหนึ่งในอัลกอริทึมแรก ๆ ที่ทำลายขอบเขตเวลาที่เป็น quadratic ถึงแม้ว่าจะพิสูจน์ได้ว่าอัลกอริทึมนี้มี running time ต่ำกว่า quadratic หลังจากที่มีการนำเสนอครั้งแรกในหลายปีต่อมาก็ตาม ในขณะทำงานแต่ละ phase นั้น shell sort ใช้การเปรียบเทียบค่าที่อยู่ในตำแหน่งที่ห่างกัน ระยะห่างดังกล่าวนี้จะลดลงลงเรื่อย ๆ จนกระทั่งถึงขั้นตอนสุดท้ายที่เป็นการเปรียบเทียบค่าที่อยู่ติดกัน ด้วยเหตุที่ระยะห่างของค่าที่นำมาเปร…

dsa:stack

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:40:51+00:00

3.3. The Stack ADT 3.3.1. Stack Model stack คือ ลิสต์ที่มีข้อจำกัดที่การดำเนินการเพิ่มและการลบโนดเกิดขึ้นได้ที่ตำแหน่งท้าย เพียงตำแหน่งเดียวเท่านั้นและจะเรียกว่า top การดำเนินการพื้นฐานที่เกิดขึ้นกับ stack คือ push ซึ่งก็คือการบรรจุ (insert) และ pop ซึ่งก็คือการลบ (delete) สมาชิกตัวสุดท้ายที่เพิ่งทำการบรรจุ เราสามารถตรวจค่าของสมาชิกตัวล่าสุดที่ได้บรรจุก่อนทำการ pop ได้ด้วยการทำงานฟังก์ชัน top โดยปกติแล้วการ top และ pop ที่ทำกับ stack ว่างนั้นถือเป็น error ใน stack ADT และการ push ลงใน stack ที…

dsa:start

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:35:09+00:00

dsa:tavltree

Anonymous (anonymous@undisclosed.example.com) — 2023-09-04T09:16:21+00:00

4.4 AVL Trees AVL (Adelson-Velskii and Landis) tree เป็น binary search tree กำกับด้วยเงื่อนไขของการสมดุล โดยเงื่อนไขการสมดุลจะต้องสามารถจัดการได้ง่ายและต้องประกันได้ว่าความลึกของทรีจะเป็น $O(log\ n)$$1.44\ log\ (N+2) – 0.328 $$log\ N$$h$$S(h)$$$S(h) = S(h – 1) + S(h – 2) + 1 \text{โนด}$$$h = 0$$S(h) = 1$$h = 1$$S(h) = 2$$O(log\ N)$…

dsa:tbistree

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:42:21+00:00

4.3 The Search Tree ADT - Binary Search Trees การประยุกต์ใช้ binary trees ที่สำคัญอย่างหนึ่ง คือ การใช้ในการค้นหาค่า สมมุติให้แต่ละโนดใน tree เก็บค่าไว้หนึ่งหน่วยข้อมูล เป็นเลขจำนวนเต็มที่มีค่าไม่ซ้ำกัน $O(log\ N)$$O(log\ N)$$O(d)$$d$$O(log\ N)$$D(N)$$N$$D(1) = 0$$i$$(N - i - 1)$$0 < i < N$$D(i)$$$D(N) = D(i) + D(N - i -1) + N -1$$$D(i)$$D(N - i -1)$$(1/N) ∑_{j=0}^{N-1}D(j)$$$D(N)=2/N [∑_{j=0}^{N-1} D(j)]+N-1$$$D(N) = O(N\ log\ N)$$O(log\ N)$$O(log\ N)$$\Theta(N^2)$$\Theta(\sqrt N)$$O(log N)$$\…

dsa:tbitree

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:41:52+00:00

4.2 Binary tree Binary tree คือทรีที่แต่ละโนดมีโนดลูกได้ไม่เกิน 2 โนด รูปที่ 4.11 แสดงรูปแบบของไบนารีทรีซึ่งประกอบด้วยรากหนึ่งโนดและทรีย่อย 2 ทรีย่อย $T_L$$T_R$$O(\sqrt N)$$O(log\ ⁡N)$$N –1$

dsa:tbtree

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:43:43+00:00

4.7 B-Trees โครงสร้างข้อมูลที่กล่าวถึงมาแล้วนั้นตั้งอยู่บนสมมติฐานที่ว่า โครงสร้างทั้งหมดสามารถจัดเก็บอยู่ในหน่วยความจำของเครื่องคอมพิวเตอร์ได้ ถ้าจำนวนข้อมูลมีปริมาณมากเกินกว่าที่จะเก็บไว้ในหน่วยความจำหลักของเครื่องได้ทั้งหมด ก็หมายความว่าต้องเก็บมันไว้ในแผ่นจานแม่เหล็ก ซึ่งกรณีเช่นนี้โมเดล Big-O ที่ใช้ในการวิเคราะห์ก็จะไม่มีความหมายอีกต่อไป ทั้งนี้เนื่องจากว่าการเข้าถึงข้อมูลในแผ่นจานแม่เหล็กนั้นใช้ค่าใช้จ่าย (เวลา) ที่แพงมากจนกระทั่ง running time ไม่มีนัยสำคัญใด ๆ อีกต่อไป$1.38\ log\ N ครั้ง…

dsa:tpreliminaries

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:41:41+00:00

4.1 Preliminaries การกำหนดนิยามให้แก่ tree สามารถทำได้หลายวิธี แต่วิธีที่ดูจะเป็นธรรมชาติคือการกำหนดนิยามแบบ recursive กล่าวคือ tree เป็น collection ของโนด (nodes) ซึ่ง collection ดังกล่าวนี้อาจเป็น collection ว่าง (empty) หรือมิฉะนั้น tree ก็จะประกอบด้วยโนดพิเศษหนึ่งโนด (ให้เป็นโนด r) และเรียกโนดนี้ว่า โนดราก (root) และอาจไม่มีหรือมีทรีย่อย (subtree) ในกรณีที่ถ้ามันไม่เป็น tree ว่าง มันก็จะประกอบด้วยทรี (ซึ่งเป็นทรีย่อย) $T1, T2, . . . , Tk$$n_1, n_2, ... , n_k$$n_i$$n_{i+1}$$1 < i < k$$\neq$$…

dsa:tree

Anonymous (anonymous@undisclosed.example.com) — 2021-09-07T10:40:05+00:00

4. Tree สำหรับปริมาณข้อมูลจำนวนมาก ๆ นั้น การเข้าถึงข้อมูลด้วยการใช้เวลาเป็น linear เป็นสิ่งที่ไม่พึงประสงค์ ในบทนี้จะกล่าวถึงโครงสร้างข้อมูลอย่างง่ายที่ส่วนใหญ่จะใช้เวลาเฉลี่ยในการทำงานเป็น $O(log\ n)$$O(log\ N)$$O(log\ N)$…

dsa:tsptree

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:42:48+00:00

4.5 Splay Trees ในหัวข้อนี้จะกล่าวถึงโครงสร้างข้อมูลที่ค่อนข้างจะไม่ซับซ้อนเรียกว่า splay tree ซึ่งเป็นโครงสร้างที่ประกันว่าการดำเนินการใด ๆ ที่กระทำต่อเนื่องกัน M ครั้งโดยเริ่มต้นการทำงานจากทรีว่างจะใช้เวลาสูงสุดเป็น $O(M\ log\ N)$$O(N)$$O(M\ f(N))$$O(f(N))$$O(log\ N)$$O(N)$$O(N)$$O(M\ log\ N)$$M$$O(N)$$O(log\ N)$$O(N)$$M$$O(M × N)$$O(N)$$∑_{i=1}^{N-1}\ i=Ω(N^2)$$O(N)$…

dsa:ttraver

Anonymous (anonymous@undisclosed.example.com) — 2021-09-08T21:42:57+00:00

4.6 Tree Traversals (Revisited) เนื่องจากภายใน binary search tree มีสารสนเทศของลำดับการจัดเรียงค่าในโนดอยู่ในตัวมัน ดังนั้นการแสดงรายการที่เป็นการจัดเรียงลำดับจึงทำได้ง่าย ดังแสดงในรูปที่ 4.56 ซึ่งเป็น recursive procedure$O(N)$$O(N)$…