3월부터 공부한 이산수학 알고리즘 개념들을 정리합니다. 교재는 Rosen의 이산수학 8판 입니다.

선형 탐색의 시간복잡도

선형 탐색의 시간 복잡도는 최상의 경우 1이며 찾는 원소가 첫 번째에 있는 경우, 최악의 경우 n으로 찾는 원소가 마지막에 있는 경우 입니다. 평균적인 시간 복잡도는 가장 자주 사용되는 최악인 경우의 시간 복잡도를 따라갑니다. 그렇기 때문에 시간 복잡도는 n이 됩니다.

문제풀이

230 페이지의 예제3 다음 리스트에서 19를 찾아보자. 리스트:[1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

use std::time::Instant;
fn main(){
    let mut tmp: Vec<i32> = vec![1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22];
    
    println!("{}",linear_search(& mut tmp,19));
}

fn linear_search(v:&mut Vec<i32>, x:i32) -> usize{
    let mut i = 1;
    let n = v.len();
    while i <= n && x != v[i]{
        i += 1;
    }
    if i <= n{
        let location = i;
        return location
    }
    else{
        let location = 0;
        return location
    }
}