zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Lecture Data Structures & Algorithms: Chapter 3

Chia sẻ: Na Na | Ngày: | Loại File: PPTX | Số trang:16

Báo xấu

82
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lecture Data Structures & Algorithms: Chapter 3 (Searching Techniques prens) presented linear (sequential) search, binary search, complexity of algorithms.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture Data Structures & Algorithms: Chapter 3

DONG NAI UNIVERSITY OF TECHNOLOGY Data Structures & Algorithms 1
DONG NAI UNIVERSITY OF TECHNOLOGY Searching Techniques 2
DONG NAI UNIVERSITY OF TECHNOLOGY LINEAR (SEQUENTIAL) SEARCH BINARY SEARCH COMPLEXITY OF ALGORITHMS 3
DONG NAI UNIVERSITY OF TECHNOLOGY • To finding out whether a particular element is present in the list. • 2 methods: linear search, binary search • The method we use depends on how the elements of the list are organized – unordered list: • linear search: simple, slow – an ordered list: • binary search or linear search: complex, faster 4
DONG NAI UNIVERSITY OF TECHNOLOGY LINEAR (SEQUENTIAL) SEARCH • How? – Proceeds by sequentially comparing the key with elements in the list – Continues until either we find a match or the end of the list is encountered. – If we find a match, the search terminates successfully by returning the index of the element – If the end of the list is encountered without a match, the search terminates unsuccessfully. 5
DONG NAI UNIVERSITY OF TECHNOLOGY LINEAR (SEQUENTIAL) SEARCH int lsearch(int arr[], int n, int value) { for(int i=0;i
DONG NAI UNIVERSITY OF TECHNOLOGY BINARY SEARCH • List must be a sorted one • We compare the element with the element placed approximately in the middle of the list • If a match is found, the search terminates successfully. • Otherwise, we continue the search for the key in a similar manner either in the upper half or the lower half. 7
DONG NAI UNIVERSITY OF TECHNOLOGY 8
void bsearch(int arr[],int n,int value) NAI UNIVERSITY OF TECHNOLOGY DONG { int low,up,mid; low = 0; up = n-1; while(low
By Recursion DONG NAI UNIVERSITY OF TECHNOLOGY int Search (int arr[], int value, int low, int up) { if (low
DONG NAI UNIVERSITY OF TECHNOLOGY COMPLEXITY OF ALGORITHMS • In Computer Science, it is important to measure the quality of algorithms, especially the specific amount of a certain resource an algorithm needs • Resources: time or memory storage (PDA?) • Different algorithms do same task with a different set of instructions in less or more time, space or effort than other. • The analysis has a strong mathematical background. • The most common way of qualifying an algorithm is the Asymptotic Notation, also 11
DONG NAI UNIVERSITY OF TECHNOLOGY COMPLEXITY OF ALGORITHMS • It is generally written as • Polynomial time algorithms, – O(1) --- Constant time --- the time does not change in response to the size of the problem. – O(n) --- Linear time --- the time grows linearly with the size (n) of the problem. – O(n2) --- Quadratic time --- the time grows quadratically with the size (n) of the problem. In big O notation, all polynomials with the same degree are equivalent, so O(3n2 + 3n + 7) = O(n2) • Sub-linear time algorithms – O(logn) -- Logarithmic time • Super-polynomial time algorithms O(n!) ; O(2n) 12
DONG NAI UNIVERSITY OF TECHNOLOGY COMPLEXITY OF ALGORITHMS • Example1: complexity of an algorithm void func ( int a[], int n ) { 2 * O(1) + O(N) cout
DONG NAI UNIVERSITY OF TECHNOLOGY COMPLEXITY OF ALGORITHMS • Example2: complexity of an algorithm void func ( int a[], int n ) { cout
DONG NAI UNIVERSITY OF TECHNOLOGY COMPLEXITY OF ALGORITHMS • Linear Search – O(n). • Binary Search – O(log2 N) 15
DONG NAI UNIVERSITY OF TECHNOLOGY END 16

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.