์ ํ ์ ๋ ฌ, Selection Sort
์
๋ ฅ : ๊ฐ์ ํ์
์ ๋ณ์๋ฅผ ๊ฐ์ง ๋ฐฐ์ด ์ถ๋ ฅ : ํด๋น ํ์
์ ์ค๋ฆ์ฐจ์ / ๋ด๋ฆผ์ฐจ์์ ๋ฐ๋ฅธ ์ ๋ ฌ๋ ๋ฐฐ์ด ๋น
์ค ํ๊ธฐ๋ฒ : O(n^2) *๋น
์ค ํ๊ธฐ๋ฒ์ ๋ํด. O(n) : ๋ชจ๋ ์์๋ฅผ ํ ๋ฒ์ฉ ๊ฑด๋๋ ค์ผ ํ๋ค๋ ๋ป. ์) ๊ฐ์ ๋ชฉ๋ก์์ ๊ฐ์๋ฅผ ์ฐพ์๋ณด์. ์ด ์ค ๊ฐ์ฅ ์ฐ์ฃผ ํ์๊ฐ ๊ฐ์ฅ ๋ง์ ๊ฐ์๋ฅผ ์ฐพ๊ธฐ ์ํด์ ๋ชจ๋ ํญ๋ชฉ์ ์ ๊ฒํด์ผํจ. -> ๋ชจ๋ ํญ๋ชฉ์ ์ ๊ฒํ๋ฏ๋ก O(n), ์ด๋ฅผ n๋ฒ ๋ฐ๋ณตํด์ ๋ชฉ๋ก์ ์ ๋ ฌํด์ผํจ. => O(n) #javascript var list = [3,55,1,33, 44, 20, 9, 7, 15, 49]; console.log("Before Selection Sort : " + list); console.log("After Selection Sort : "); console.log(selec..
2019. 5. 19.
๋จ์ ํ์, Simple Search
์
๋ ฅ : ์ ๋ ฌ๋ ๋ฐฐ์ด ์ถ๋ ฅ : ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ์ฐพ๋ ์์๊ฐ ์กด์ฌํ๋ฉด ํด๋น ์ธ๋ฑ์ค, ์์ผ๋ฉด null. ๋น
์คํ๊ธฐ๋ฒ : O(n) #javascript //์ ๋ ฌ๋ ๋ฐฐ์ด var list=[1,2,3,4,5,7,10,33,57]; //์ฐพ๊ณ ์ ํ๋ ๊ฐ var search = 57; function simpleSearch(_list, find) { var idx = -1; for(var i = 0 ; i < _list.length; ++i) { if( _list[i] == find) { idx = i; break; } } return idx; } console.log("Simple Search : " + simpleSearch(list, search)); ์ฝ๋๊ฐ ๊ฐ๋จํ์ง๋ง. ์ต์
์ ๊ฒ์๋ฐฉ๋ฒ์ด๋ค. ๋ง์ฝ 1์ต๊ฐ์ ์ด๋ฆ์ด ..
2019. 5. 19.
์ด์ง ํ์, Binary Search
์
๋ ฅ : ์ ๋ ฌ๋ ์์ ๋ฆฌ์คํธ ์ถ๋ ฅ : ์
๋ ฅ๋ฐ์ ์์ ๋ฆฌ์คํธ์์ ์ฐพ๋ ๊ฐ์ด ์์ผ๋ฉด null์ ๋ฐํ, ์ฐพ์ผ๋ฉด ๋ฆฌ์คํธ์์ ์ธ๋ฑ์ค(์์น)๋ฅผ ๋ฐํ. ๋น
์ค ํ๊ธฐ๋ฒ : O(log n) #javascript //์ ๋ ฌ๋ ๋ฐฐ์ด var list=[1,2,3,4,5,7,10,33,57]; //์ฐพ๊ณ ์ ํ๋ ๊ฐ var search = 33; function binarySearch(list , find) { var start = 0; var end = list.length-1; var cnt = 1; var mid =-1; while(1) { //๊ทธ๋ฅ ๋๋๊ธฐ 2๋ฅผ ํ๋๋ ์์์ ๊ฐ์ด ์ถ๋ ฅ๋์ด์ idx๊ณ์ฐ์ด ์๋๋๋ผ. //๊ฐ์ ๋ก ํ๋ณํ. mid = parseInt((start+end)/2); //ํด๋น ๋ฐฐ์ด์ ๊ฐ์ฅ ์ค๊ฐ๊ฐ์ ์ ํ. v..
2019. 5. 19.