알고리즘 그래 픽 학습 노트 - 이분법, 링크, 배열

1. 이분법 찾기

def binary_search(list,item):
    low=0 #              
    high=len(list)-1#              
    while low<=high: #                             
        mid=(low+high)//2#           
        guess=list[mid]
        if guess==item:#     ，        
            return mid
        elif guess>item:high=mid-1#     ，                 -1
        else:low=mid+1#     ，                 +1
    return None #         ，    
if __name__=='__main__':
    my_list=[1,3,5,7,9,11,13,15,17]
    print(binary_search(my_list,15))

 여행사 문제:
한 여행사 가 다섯 도시 에 가 려 고 한다 면 그 는 5 가 있다!가장 짧 은 노선 을 고 르 려 면 120 번 의 조작 을 해 야 한다.이 알고리즘 의 운행 시간 은 O (n!) 이다.

2 점 검색 속도 가 간단 한 검색 보다 훨씬 빠르다

O (logn) 가 O (n) 보다 빠르다.검색 해 야 할 요소 가 많 을 수록 전 자 는 후자 보다 훨씬 빠르다

알고리즘 운행 시간 은 초 단위 가 아 닙 니 다

알고리즘 운행 시간 은 성장 속도 의 측면 에서 측정 된다

.

알고리즘 운행 시간 을 대 O 표현법 으로 표시

2. 배열 과 링크
1. 메모리 작업 원리
메모리 가 캐비닛 이 고 캐비닛 안에 서랍 이 많다.
메모리 에 데 이 터 를 저장 해 야 할 때 는 컴퓨터 에 저장 공간 을 제공 해 달라 고 요청 하고 컴퓨터 는 저장 주 소 를 제공 합 니 다.
여러 가지 데 이 터 를 저장 해 야 할 때 는 두 가지 기본 방식 이 있 습 니 다. - 배열 과 링크.
2. 배열 과 링크
배열
업무 관리 프로그램 을 만 들 려 면 이 업무 항목 을 메모리 에 저장 해 야 합 니 다.
배열 을 사용 하 는 것 은 모든 업무 가 메모리 에 연결 되 어 있다 는 것 을 의미한다.
예 를 들 어:
우 리 는 처리 해 야 할 사건 을 '파일' 로 보고 메모 리 를 '서랍' 으로 보고 모든 '서랍' 을 '파일' 로 놓는다.
네 개의 업무 사건 을 서랍 에 넣 어야 한다. 세 개 를 넣 었 을 때 네 번 째 서랍 에 다른 사람의 물건 이 놓 여 있 는 것 을 발견 했다.
이 럴 때, 너 는 컴퓨터 로 하여 금 네 개의 서 류 를 수용 할 수 있 는 서랍 을 하나 더 주 고, 서 류 를 네 개의 서랍 에 하나씩 넣 게 할 수 밖 에 없다.
다시 예 를 들 면:
너 와 너의 친 구 는 영 화 를 보 러 갔다. 세 사람 자 리 를 산 후에 갑자기 친구 가 왔 지만 원래 의 자 리 는 빈자리 가 없 었 다.이 럴 때 는 모두 가 앉 을 수 있 는 자 리 를 하나 더 찾 을 수 밖 에 없어.
이렇게 새로운 친구 가 오 면 다시 자 리 를 옮 겨 야 하 는데 어떻게 해결 해 야 할 까?
한 가지 방법 은 좌석 을 예약 하고 세 사람 이 영 화 를 보고 10 중대 좌석 을 찾 는 것 이다. 그러면 7 명의 친구 가 더 와 도 자 리 를 바 꿀 필요 가 없다.
그러나 이런 방법 은 두 가지 단점 이 있다.
첫째, 많이 나 온 자 리 는 전혀 사용 할 수 없 을 수도 있 습 니 다. 이것 은 자원 에 대한 낭비 입 니 다.
둘째, 여덟 번 째 친구 가 왔 을 때 너 는 또 이동 해 야 한다.
이런 문제 에 대해 서 는 링크 로 해결 할 수 있다.
체인 테이블
링크 의 요 소 는 메모리 의 어느 곳 에 나 저장 할 수 있다.
링크 의 모든 요 소 는 다음 요소 의 주 소 를 저장 하여 일련의 무 작위 메모리 주 소 를 연결 시 켰 다.
이것 은 보물 찾기 게임 과 같 습 니 다. 첫 번 째 주소 로 갈 때 두 번 째 주소 의 좌 표를 얻 고 순서대로 찾 습 니 다.
따라서 링크 에 요 소 를 추가 하 는 것 은 쉽 습 니 다. 값 은 메모리 에 넣 고 주 소 를 이전 요소 에 저장 해 야 합 니 다.
이렇게 하면 영 화 를 보 는 문 제 를 완벽 하 게 해결 할 수 있다. 링크 는 '우 리 는 따로 앉 지만 한 사람의 자 리 를 통 해 다음 사람의 자 리 를 찾 을 수 있다' 는 것 과 같다.
충분 한 메모리 공간 만 있 으 면 링크 에 메모 리 를 분배 할 수 있다.
링크 의 장점 은 바로 요 소 를 삽입 하 는 데 나타난다.