VietTuts

Tự Học Lập Trình Online

  • Home
  • Java
  • Servlet
  • JSP
  • Struts2
  • Hibernate
  • Spring
  • MyBatis
  • Java WS
  • C
  • C++
  • C#
  • Python
  • PHP
  • Excel
  • VBA
  • Web
    • JavaScript
    • JQUERY
    • JSON
    • AJAX
    • CSS
    • HTML
    • HTML5
    • Node.js
    • Angular 7
  • SQL
    • MySQL
    • SQL Server
  • Misc
    • Eclipse
    • Phần mềm tiện ích
    • Cấu trúc DL&GT
    • Selenium Test

Cấu Trúc Dữ Liệu & Giải Thuật

Tổng quan về cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu là gì? Giải thuật là gì? Cài đặt môi trường

Giải Thuật

Giải thuật tiệm cận Giải thuật tham lam Giải thuật chia để trị Giải thuật qui hoạch động

Cấu Trúc Dữ Liệu Mảng

Cấu trúc dữ liệu mảng

Danh sách liên kết - Linked list

Cấu trúc dữ liệu Linked List Cấu trúc dữ Doubly Linked List Cấu trúc dữ Circular Linked List

Ngăn Xếp & Hàng Đợi

Cấu trúc dữ liệu ngăn xếp - Stack Cấu trúc dữ hàng dợi - Queue

Một Số Giải Thuật Tìm Kiếm

Tìm kiếm tuyến tính - Linear Search Tìm kiếm nhị phân - Binary Search Tìm kiếm nội suy - Interpolation Search Cấu trúc dữ liệu Hash Table

Một Số Giải Thuật Sắp Xếp

Giải thuật sắp xếp Sắp xếp nổi bọt - Bubble Sort Sắp xếp chèn - Insertion Sort Sắp xếp chọn - Selection Sort Sắp xếp trộn - Merge Sort Sắp xếp nhanh - Quick Sort Giải thuật Shell Sort Giải thuật quay lui - Back Tracking

Cấu Trúc Dữ Liệu Đồ Thị (Graph)

Cấu trúc dữ liệu đồ thị Tìm kiếm theo chiều sâu - Depth First Search Tìm kiếm theo chiều sâu - Breadth First Search
1 / 3
❮ ❯

Giải thuật Tìm kiếm nội suy (Interpolation Search)


Giải thuật tìm kiếm nhị phân (Binary Search)
Cấu trúc dữ liệu Hash Table

Nội dung chính

  • Giải thuật Tìm kiếm nội suy (Interpolation Search) là gì?
  • Xác định vị trí trong Binary Search
  • Dò vị trí trong Tìm kiếm nội suy (Interpolation Search)
  • Giải thuật Tìm kiếm nội suy
  • Code mẫu cho giải thuật Tìm kiếm nội suy

Giải thuật Tìm kiếm nội suy (Interpolation Search) là gì?

Tìm kiếm nội suy (Interpolation Search) là biến thể cải tiến của tìm kiếm nhị phân (Binary Search). Để giải thuật tìm kiếm này làm việc chính xác thì tập dữ liệu phải được sắp xếp.

Binary Search có lợi thế lớn về độ phức tạp thời gian khi so sánh với Linear Search. Linear Search có độ phức tạp trường hợp xấu nhất là Ο(n) trong khi Binary Search là Ο(log n).

Có một số tình huống mà vị trí của dữ liệu cần tìm có thể đã được biết trước. Ví dụ, trong trường hợp danh bạ điện thoại, nếu chúng ta muốn tìm số điện thoại của Hương chẳng hạn. Trong trường hợp này, Linear Search và cả Binary Search có thể là chậm khi thực hiện tìm kiếm, khi mà chúng ta có thể trực tiếp nhảy tới phần không gian bộ nhớ có tên bắt đầu với H được lưu giữ.



Xác định vị trí trong Binary Search

Trong Binary Search, nếu dữ liệu cần tìm không được tìm thấy thì phần còn lại của danh sách được phân chia thành hai phần: phần bên trái (chứa giá trị nhỏ hơn) và phần bên phải (chứa giá trị lớn hơn). Sau đó tiến trình tìm kiếm được thực hiện trên một trong hai phần này.

Giải thuật tìm kiếm nhị phân (Binary Search) Giải thuật tìm kiếm nhị phân (Binary Search) Giải thuật tìm kiếm nhị phân (Binary Search) Giải thuật tìm kiếm nhị phân (Binary Search)

Dò vị trí trong Tìm kiếm nội suy (Interpolation Search)

Tìm kiếm nội suy tìm kiếm một phần tử cụ thể bằng việc tính toán vị trí dò (Probe Position). Ban đầu thì vị trí dò là vị trí của phần tử nằm ở giữa nhất của tập dữ liệu.

Giải thuật Tìm kiếm nội suy (Interpolation Search) Giải thuật Tìm kiếm nội suy (Interpolation Search)

Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Để chia danh sách thành hai phần, chúng ta sử dụng phương thức sau:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
Trong đó:
   A    = danh sách
   Lo   = chỉ mục thấp nhất của danh sách
   Hi   = chỉ mục cao nhất của danh sách
   A[n] = giá trị được lưu giữ tại chỉ mục n trong danh sách

Nếu phần tử cần tìm có giá trị lớn hơn phần tử ở giữa thì phần tử cần tìm sẽ ở mảng con bên phải phần tử ở giữa và chúng ta lại tiếp tục tính vị trí dò; nếu không phần tử cần tìm sẽ ở mảng con bên trái phần tử ở giữa. Tiến trình này tiến tụp diễn ra trên các mảng con cho tới khi kích cỡ của mảng con giảm về 0.

Độ phức tạp thời gian chạy của Interpolation Search là Ο(log (log n)), trong khi của Binary Search là Ο(log n).



Giải thuật Tìm kiếm nội suy

Bởi vì đây là sự cải tiến của giải thuật Binary Search nên chúng ta sẽ chỉ đề cập tới các bước để tìm kiếm chỉ mục của giá trị cần tìm bởi sử dụng vị trí dò.

Bước 1 : Bắt đầu tìm kiếm dữ liệu từ phần giữa của danh sách
Bước 2 : Nếu đây là một so khớp (một kết nối), thì trả về chỉ mục của phần tử, và thoát.
Bước 3 : Nếu không phải là một so khớp, thì là vị trí dò.
Bước 4 : Chia danh sách bởi sử dụng phép tính tìm vị trí dò và tìm vị trí giữa mới.
Bước 5 : Nếu dữ liệu cần tìm lớn hơn giá trị tại vị trí giữa, thì tìm kiếm trong mảng con bên phải.
Bước 6 : Nếu dữ liệu cần tìm nhỏ hơn giá trị tại vị trí giữa, thì tìm kiếm trong mảng con bên trái
Bước 7 : Lặp lại cho tới khi tìm thấy so khớp

Code mẫu cho giải thuật Tìm kiếm nội suy


A → Mảng
N → Kích cỡ của A
X → Giá trị cần tìmhàm tìm kiếm nội suy Interpolation_Search()
   Gán Lo  →  0
   Gán Mid → -1
   Gán Hi  →  N-1
   While X không so khớp
   
      if Lo bằng Hi OR A[Lo] bằng A[Hi]
         EXIT: Thất bại, không tìm thấy X
      kết thúc if
      
      Gán Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
      if A[Mid] = X
         EXIT: Thành công, tìm thấy tại Mid
      else 
         if A[Mid] < X
            Thiết lập Lo thành Mid+1
         else if A[Mid] > X
            Thiết lập Hi thành Mid-1
         kết thúc if
      kết thúc if
   Kết thúc While
Kết thúc hàm

Giải thuật tìm kiếm nhị phân (Binary Search)
Cấu trúc dữ liệu Hash Table

Recent Updates

Sắp Tết 2024 Rồi! - Còn bao nhiêu ngày nữa là đến tết 2024?Java Swing - Bài tập quản lý sinh viên trong javaLinkedList trong javaArrayList trong javaBài tập java có lời giảiXác thực dữ liệu (Data Validation) trong ExcelSắp xếp dữ liệu trong ExcelLọc dữ liệu (Data Filter) trong ExcelHeader và Footer trong ExcelMàu văn bản và màu nền (background) trong ExcelCăn chỉnh văn bản trong ExcelĐịnh hướng văn bản trong ExcelTrang trí văn bản trong Excel

VietTuts on facebook

Học Lập Trình Online Miễn Phí - VietTuts.Vn
Danh Sách Bài Học

Học Java | Hibernate | Spring
Học Excel | Excel VBA
Học Servlet | JSP | Struts2
Học C | C++ | C#
Học Python
Học SQL

Bài Tập Có Lời Giải

Bài tập Java
Bài tập C
Bài tập C++
Bài tập C#
Bài tập Python
Ví dụ Excel VBA

Câu Hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java
25 câu hỏi phỏng vấn servlet
75 câu hỏi phỏng vấn jsp
52 câu hỏi phỏng vấn Hibernate
70 câu hỏi phỏng vấn Spring
57 câu hỏi phỏng vấn SQL

Scroll back to top

Copyright © 2016 VietTuts.Vn all rights reserved. | Liên hệ | Chính sách - riêng tư | sitemap.html | sitemap_index.xml