[일반] 아래 점근표기법 오개념글 보고 위키피디아 보는데

[익명(1.236)]

https://ko.m.wikipedia.org/wiki/%EC%B5%9C%EC%84%A0,_%EC%B5%9C%EC%95%85,_%EA%B7%B8%EB%A6%AC%EA%B3%A0_%ED%8F%89%EA%B7%A0%EC%9D%98_%EA%B2%BD%EC%9A%B0


https://m.dcinside.com/board/ps/43714?page=2
한국어랑 영어랑 내용이 다르네ㅡㅡ
버블정렬 최선일 때 O(n) 맞지?

[익명(1.236)]

그와중에 링크 중간에 반점 들어갔다고 깨지네

[익명(117.111)]

버블은 무조건 다 봐야지않냐? 삽입정렬이 이미 정렬된 상태면 횟수 확 줄고 - dc App

[익명(117.111)]

다봐야한다는게 모든 두 쌍씩 다 보는 거 - dc App

[익명(211.234)]

구현마다 언제 종료하냐에 차이는 있을텐데 한 번 훑으면서 swap 없을 때 종료시킨다면 정렬된 상태에서 최선은 선형일 듯

[익명(117.111)]

에이 그러면 모든 정렬이 최선의 경우 n이지 초반에 한 번 훑어보고 정렬된 상태아니면 원래 정렬 알고리즘 실행하게하면 되겠네 - dc App

[익명(211.234)]

그게 맞지 않나? 너가 말한 이미 정렬되었는지 슥 훑는 과정이 없을 때 내부적으로 정렬된 걸 확인하고 중도 종료하는 과정의 복잡도가 얼마인지 보는 게 최선 케이스 아닌가?

[익명(117.111)]

사실 나도 잘 모름 - dc App

[익명(211.234)]

헉