Chào các bạn!
Tiếp theo chuỗi series về các thuật toán sắp xếp và tìm kiếm căn bản, thì ở bài viết này mình sẽ trình bày các bạn phần thuật toán tìm kiếm tuần tự.
Thuật toán khá đơn giản, nên chắc cũng không cần vòng vo nhiều nữa, chúng ta vào chi tiết ngay nhé.
Đặt vấn đề
Cho dãy số có kích thước N phần tử và số X. Hãy xác định vị trí đầu tiên mà X xuất hiện trong dãy số.
Ý tưởng thuật toán
Lần lượt duyệt qua từng phần tử và kiểm tra, nếu gặp X thì thoát và trả về giá trị vị trí.
Và dưới đây là code mà mình đã chuẩn bị:
1 2 3 4 5 6 7 | <span class="token keyword">int</span> <span class="token function">linearSearch</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>arr<span class="token punctuation">,</span> <span class="token keyword">int</span> X<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator"><</span>sz<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>X <span class="token operator">==</span> arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">return</span> i<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Full code bạn có thể xem ở đây: https://ideone.com/Hc5Fb8
Đánh giá độ phức tạp
Dễ thấy rằng, độ phức tạp của giải thuật trên là
O(N)O(N), nhưng tùy theo vị trí của
XX ở đâu mà xác định thời gian nhanh hay chậm.
Và nếu bạn nhấn vào link full code ở phía trên, bạn sẽ tìm thấy dòng
Total time for search: 3(s)
Đoạn code trên mình đã tạo ra dãy số 10tr số tự nhiên đầu tiên bỏ vào dãy arr. Rồi sau đó sinh ngẫu nhiên số X nằm trong dãy số, rồi tìm kiếm trong 1000 lần.
Thì tổng thời gian tìm kiếm là tầm 3s.
Kết luận
Trên đây, mình đã trình bày các bạn về thuật toán Linear Search. Bài tiếp theo chúng ta sẽ cùng tìm hiểu về thuật toán tìm kiếm nhị phân nhé. Nó sẽ mạnh mẽ hơn thuật toán này gấp nhiều lần.
Nếu bạn có bất cứ ý kiến nào đóng góp, xin hãy gửi comment, mình sẽ trả lời và khắc phục cho những lần sau.