Độ phức tạp về thời gian của tìm kiếm tuyến tính trong python

Thuật toán tìm kiếm là một khái niệm khoa học máy tính cơ bản mà bạn nên hiểu với tư cách là nhà phát triển. Chúng hoạt động bằng cách sử dụng phương pháp từng bước để định vị dữ liệu cụ thể trong tập hợp dữ liệu

Trong bài viết này, chúng ta sẽ tìm hiểu cách các thuật toán tìm kiếm hoạt động bằng cách xem xét cách triển khai của chúng trong Java và Python

Thuật toán tìm kiếm là gì?

Theo Wikipedia, một thuật toán tìm kiếm là

Bất kỳ thuật toán nào giải quyết vấn đề tìm kiếm, cụ thể là truy xuất thông tin được lưu trữ trong một số cấu trúc dữ liệu hoặc được tính toán trong không gian tìm kiếm của miền vấn đề, với các giá trị rời rạc hoặc liên tục

Các thuật toán tìm kiếm được thiết kế để kiểm tra hoặc truy xuất một phần tử từ bất kỳ cấu trúc dữ liệu nào mà phần tử đó đang được lưu trữ. Họ tìm kiếm mục tiêu (khóa) trong không gian tìm kiếm

Các loại thuật toán tìm kiếm

Trong bài đăng này, chúng ta sẽ thảo luận về hai loại thuật toán tìm kiếm quan trọng

  1. Tìm kiếm tuyến tính hoặc tuần tự
  2. Tìm kiếm nhị phân

Hãy thảo luận chi tiết về hai vấn đề này với các ví dụ, triển khai mã và phân tích độ phức tạp về thời gian

Tìm kiếm tuyến tính hoặc tuần tự

Thuật toán này hoạt động bằng cách lặp lại tuần tự toàn bộ mảng hoặc danh sách từ một đầu cho đến khi tìm thấy phần tử đích. Nếu phần tử được tìm thấy, nó sẽ trả về chỉ mục của nó, ngược lại -1

Bây giờ hãy xem một ví dụ và cố gắng hiểu nó hoạt động như thế nào

arr = [2, 12, 15, 11, 7, 19, 45]

Giả sử phần tử mục tiêu mà chúng tôi muốn tìm kiếm là  

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
3

Phương pháp tìm kiếm tuyến tính hoặc tuần tự

  • Bắt đầu với chỉ số 0 và so sánh từng phần tử với mục tiêu
  • Nếu mục tiêu được tìm thấy bằng với phần tử, hãy trả về chỉ mục của nó
  • Nếu không tìm thấy mục tiêu, trả về -1

Triển khai mã

Bây giờ hãy xem cách chúng tôi triển khai loại thuật toán tìm kiếm này trong một vài ngôn ngữ lập trình khác nhau

Tìm kiếm tuyến tính hoặc tuần tự trong Java

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}

Tìm kiếm tuyến tính hoặc tuần tự trong Python

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

if __name__ == '__main__':
    nums = [2, 12, 15, 11, 7, 19, 45]
    target = 7
    print(search(nums, target))

Phân tích độ phức tạp thời gian

Trường hợp tốt nhất xảy ra khi phần tử đích là phần tử đầu tiên của mảng. Số lần so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp thời gian là

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
4

Trường hợp trung bình. Trung bình, phần tử đích sẽ ở đâu đó ở giữa mảng. Số lần so sánh, trong trường hợp này, sẽ là N/2. Vì vậy, độ phức tạp của thời gian sẽ là

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
5 (hằng số bị bỏ qua)

Trường hợp xấu nhất xảy ra khi phần tử đích là phần tử cuối cùng trong mảng hoặc không có trong mảng. Trong trường hợp này, chúng ta phải duyệt qua toàn bộ mảng và do đó số phép so sánh sẽ là N. Vì vậy, độ phức tạp thời gian sẽ là

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
5

Tìm kiếm nhị phân

Loại thuật toán tìm kiếm này được sử dụng để tìm vị trí của một giá trị cụ thể có trong một mảng được sắp xếp. Thuật toán tìm kiếm nhị phân hoạt động theo nguyên tắc chia để trị và nó được coi là thuật toán tìm kiếm tốt nhất vì chạy nhanh hơn

Bây giờ, hãy lấy một mảng đã sắp xếp làm ví dụ và cố gắng hiểu cách thức hoạt động của nó

arr = [2, 12, 15, 17, 27, 29, 45]

Giả sử phần tử mục tiêu được tìm kiếm là  

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
7

Phương pháp tìm kiếm nhị phân

  • So sánh phần tử đích với phần tử ở giữa của mảng
  • Nếu phần tử đích lớn hơn phần tử ở giữa thì tìm kiếm tiếp tục ở nửa bên phải
  • Ngược lại, nếu phần tử đích nhỏ hơn giá trị ở giữa, quá trình tìm kiếm sẽ tiếp tục ở nửa bên trái
  • Quá trình này được lặp lại cho đến khi phần tử ở giữa bằng phần tử đích hoặc phần tử đích không có trong mảng
  • Nếu phần tử đích được tìm thấy, chỉ mục của nó được trả về, nếu không thì trả về -1

Triển khai mã

Tìm kiếm nhị phân trong Java

package algorithms.searching;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 17, 27, 29, 45};
        int target = 17;
        System.out.println(search(nums, target));
    }

    static int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > target)
                end = mid - 1;
            else if (nums[mid] < target)
                start = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Tìm kiếm nhị phân trong Python

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
0

Phân tích độ phức tạp thời gian

Trường hợp tốt nhất xảy ra khi phần tử đích là phần tử ở giữa của mảng. Số lần so sánh, trong trường hợp này, là 1. Vì vậy, độ phức tạp thời gian là

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
4

Trường hợp trung bình. Trung bình, phần tử đích sẽ ở đâu đó trong mảng. Vì vậy, độ phức tạp thời gian sẽ là

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
9

Trường hợp xấu nhất xảy ra khi phần tử đích không có trong danh sách hoặc nó cách xa phần tử ở giữa. Vì vậy, độ phức tạp thời gian sẽ là

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
9

Cách tính độ phức tạp của thời gian

Giả sử phép lặp trong Tìm kiếm nhị phân kết thúc sau k lần lặp

Tại mỗi lần lặp, mảng được chia cho một nửa. Vì vậy, giả sử độ dài của mảng tại bất kỳ lần lặp nào là N

Ở lần lặp 1,

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
4

Ở lần lặp 2,

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
5

Ở lần lặp 3,

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
6

Tại lần lặp k,

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
7

Ngoài ra, chúng ta biết rằng sau k lần chia, độ dài của mảng trở thành 1. Độ dài của mảng = N⁄2k = 1=> N = 2k

Nếu chúng ta áp dụng chức năng nhật ký trên cả hai mặt. log2 (N) = log2 (2k)=> log2 (N) = k log2 (2)

As (loga (a) = 1)
Do đó,=> k = log2 (N)

Vì vậy, bây giờ chúng ta có thể thấy tại sao độ phức tạp về thời gian của Tìm kiếm nhị phân là log2 (N)

Bạn cũng có thể hình dung hai thuật toán trên bằng công cụ đơn giản do Dipesh Patil xây dựng - Algorithms Visualizer

Tìm kiếm nhị phân theo thứ tự

Giả sử, chúng ta phải tìm một phần tử đích trong một mảng được sắp xếp. Chúng tôi biết rằng mảng được sắp xếp, nhưng chúng tôi không biết liệu nó được sắp xếp theo thứ tự tăng dần hay giảm dần

Phương pháp tìm kiếm nhị phân theo thứ tự

Cách thực hiện tương tự như tìm kiếm nhị phân ngoại trừ việc chúng ta cần xác định xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Điều này sau đó cho phép chúng tôi đưa ra quyết định về việc tiếp tục tìm kiếm ở nửa bên trái của mảng hay nửa bên phải của mảng

  • Trước tiên chúng tôi so sánh mục tiêu với phần tử ở giữa
  • Nếu mảng được sắp xếp theo thứ tự tăng dần và mục tiêu nhỏ hơn phần tử ở giữa HOẶC mảng được sắp xếp giảm dần và mục tiêu lớn hơn phần tử ở giữa, thì chúng ta tiếp tục tìm kiếm ở nửa dưới của mảng bằng cách đặt
    def search(nums, target):
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1
    
    if __name__ == '__main__':
        nums = [2, 12, 15, 11, 7, 19, 45]
        target = 7
        print(search(nums, target))
    1
  • Mặt khác, chúng tôi thực hiện tìm kiếm ở nửa trên của mảng bằng cách đặt
    def search(nums, target):
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1
    
    if __name__ == '__main__':
        nums = [2, 12, 15, 11, 7, 19, 45]
        target = 7
        print(search(nums, target))
    2

Điều duy nhất chúng ta cần làm là tìm hiểu xem mảng được sắp xếp theo thứ tự tăng dần hay giảm dần. Chúng ta có thể dễ dàng tìm thấy điều này bằng cách so sánh các phần tử đầu tiên và cuối cùng của mảng

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
0

Triển khai mã

Tìm kiếm nhị phân theo thứ tự trong Java

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
1

Tìm kiếm nhị phân theo thứ tự trong Python

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}
2

Phân tích độ phức tạp thời gian

Sẽ không có thay đổi về độ phức tạp của thời gian, vì vậy nó sẽ giống như Tìm kiếm nhị phân

Sự kết luận

Trong bài viết này, chúng ta đã thảo luận về hai trong số các thuật toán tìm kiếm quan trọng nhất cùng với cách triển khai mã của chúng trong Python và Java. Chúng tôi cũng đã xem xét phân tích độ phức tạp thời gian của họ

Cảm ơn vì đã đọc

Đăng ký nhận bản tin của tôi

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO


Độ phức tạp về thời gian của tìm kiếm tuyến tính trong python
Ashutosh Krishna

Nhà phát triển ứng dụng tại Thoughtworks Ấn Độ


Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn

Học cách viết mã miễn phí. Chương trình giảng dạy nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có việc làm với tư cách là nhà phát triển. Bắt đầu

Độ phức tạp của tìm kiếm tuyến tính là gì?

Do đó, độ phức tạp của tìm kiếm tuyến tính là O(n) . Nếu phần tử được tìm kiếm tồn tại trên khối bộ nhớ đầu tiên thì độ phức tạp sẽ là. Ô(1). Mã cho chức năng tìm kiếm tuyến tính trong JavaScript được hiển thị bên dưới. Hàm này trả về vị trí của mục chúng ta đang tìm kiếm trong mảng.

Độ phức tạp thời gian của thuật toán tuyến tính là gì?

Độ phức tạp về thời gian của Tìm kiếm tuyến tính trong trường hợp tốt nhất là O(1) . Trong trường hợp xấu nhất, độ phức tạp thời gian là O(n).

Độ phức tạp thời gian của tìm kiếm tuyến tính và tìm kiếm nhị phân là gì?

Biểu đồ so sánh

Thuật toán tìm kiếm nhanh nhất trong Python là gì?

Nếu bạn biết rằng phần tử bạn đang tìm kiếm có khả năng nằm gần đầu mảng hơn, bạn có thể sử dụng tìm kiếm theo cấp số nhân. Nếu mảng đã sắp xếp của bạn cũng được phân phối đồng đều, thì thuật toán tìm kiếm nhanh nhất và hiệu quả nhất để sử dụng sẽ là tìm kiếm nội suy .