1. n^2 인 프로그램과 2^n 인 프로그램이 있다고 가정하자. 입력값이 6 일때는 각각 36초, 64초가 걸린다. 그런데 입력값이 100 일때는 n^2인 프로그램은 몇시간이면 끝나지만, 2^n 인 프로그램은 우주의 나이의 10억배가 걸린다. 2. 따라서 컴퓨터가 아무리 발전해도 효율적인 알고리즘은 항상 중요하다. 3. 효율적인 알고리즘이란 수행시간이 짧으면서, 컴퓨터의 자원을 덜 사용하는 것 이다. 4. 수행시간을 계산하는 확실한 방법은 실행시키고 그 시간을 측정하면 된다. 5. c언어에서는 time 헤더파일에 있는 clock() 함수를 사용해서 사용된 cpu 시간을 계산하면 된다. 알고리즘 시작 시간과, 끝난 시간의 차이를 계산하면 된다. 6. 위 방법은 확실하지만, 치명적인 단점이 있다. 일단 시간 측정을 위해 알고리즘 구현을 해야하고 또 시간을 들여 테스트를 해야한다는 것이다. 7. 뿐만아니라 하드웨어 차이와 소프트웨어 환경에 따라 수행속도가 달라진다. 8. 위와 같은 문제 때문에, 직접 구현하지 않고서도 알고리즘의 효율성을 비교할 필요성이 있다. 9. 그래서 알고리즘 복잡도 분석(Complexity analysis) - (시간, 공간) 을 한다. 10. 우리는 수행시간 분석(시간 복잡도) 에 관심을 둔다. 기억공간 분석(공간 복잡도) 은 우리 일이 아니다. 11. 이를 위해 수행시간을 계산할 수 있는 함수를 만든다. 근데 이제 'time' 이 아니라. 'step' 이다. (당연히 함수값은 낮을수록 좋은것이다.) 12. 연산의 수(step)를 입력의 개수 n 의 함수로 나타낸것을 시간 복잡도 함수 라고 하고 , T(n) 이라 한다. 중요하건 이름은 시간 복잡도인데. time 이 아니라 step 이라는 점. 13. T(n) = n^2 + n + 1 이라고 가정하자. 입력의 개수 n 이 1000 이라면 최고 차항을 제외한 나머지 값은 전체의 0.1% 이다. 14. 입력값이 커짐에 따라 최고 차항의 비중은 99.9999999..% 가 된다. 따라서 시간복잡도 함수는 가장 큰 항만 고려한다. 15. 따라서 시간 복잡도 함수에서 중요한것은, 연산의 총 횟수가 n에 비례하여 어떤 증가 추세를 가지고 있는가이다. 16. n^2 만 남기니까 보기쉽고, 비교가 편하다. 이런 방식을 빅오 표기법 (Big - O - Notation) 이라고 한다. 17. 한마디로 빅오 표기법은, 상한(가장 큰 차수)이다. 18. 물론 입력값이 작거나( n = 1,2,3 ) 상수항이나 계수가 큰 경우 (10^2000) 수행시간에 영향을 준다. 빅오가 의미가 없다. 19. 또 당연히 빅오는 만능이 아니다. 상한 이므로 여러개가 존재할 수 있다. 어떤 함수보다 항상 더 큰 함수가 있다면, 그 함수를 써도 되는거다. 20. 그 문제점을 보완하기 위하여 빅오메가 , 빅세타 표기법이 있다. 21. 하한을 표시하는 방법은 빅 오메가이다. 22. 상한(빅오) 하한(빅오메가) 모두 표시가 가능할 경우. 빅 세타 표기법을 쓴다. 당연히 가장 정밀하다 23. 근데 통상적으로 빅오 표기법을 많이 사용한다. 이때는 최소차수로 상한을 표시한다고 가정을 한 것이다. 24. 마무리 25. 그럼 이제 빅오 표기법을 통해 알고리즘을 구분하고, 수행시간을 분석 한다고 할 때, 입력값으로 어떤걸 넣어야 할까 26. 최선(정렬 알고리즘에 정렬된거 넣음), 평균(모든 입력을 고려하고 입력 발생 확률까지 고려), 최악(가장 오래 걸림) 이 있다. 27. 비행기 관제 업무에 사용되는 알고리즘은, 어떤 입력이 들어와도 일정한 시간 한도 안에 반드시 계산을 끝마쳐야 한다. 아니면 대형 사고가 발생한다. 28. 따라서 최악의 경우가 중요한 의미를 가진다. 최선( 최선이면 그냥 그대로 데이터 쓰면 됨 ), 평균( 구하기가 힘듬 ) 29. 돈포겟투잇김치 30. 사랑해요 바이바이
Big O = 선형 시간복잡도 O(1) = 상수(일정 시간) = 인풋 숫자 +n : step 숫자 =1 O(n) = 선형 검색 = 인풋 숫자 +n : step 숫자 +n O(n^2) = 2차 시간 = 인풋 숫자 +n : step 숫자 n^2 O(log n) = 이진 검색(로그 시간) = 인풋 숫자 +n : step 숫자 n/2 로그 지수
알고리즘이 중요한 것이 문법만 배워서는 올바른 프로그래머가 될 수 없기 때문이죠. 문법만 가지고 누구나 코딩을 할 수 있지만 과연 올바른 코딩을 할 수 있냐하는 문제가 있죠. 효율적인 코딩이 안되면 로딩하는데 시간도 오래 걸리고 자주 엉키고... 엉망진창이 됩니다. 버그가 많아지죠. 그래서 알고리즘을 익히는게 중요합니다. 예컨데 알고리즘을 모르는 사람은 for문을 남발하는 경향이 있죠. for문 하나 쓸때마다 얼마나 느려지는지 안다면 for문은 최소한만 쓰게 되죠. 이중/삼중으로 써버리면 정말 느려집니다. 자료구조.... 자료구조를 배우다보면 그 심오함에 무릅을 탁 치게되는 경우가 많습니다. 다들 함 배워보시면 압니다. 개인적으로 자료구조와 알고리즘은 씨언어 문법을 배우고 나서 씨언어를 이용한 자료구조/알고리즘을 배울것을 권장합니다. 자바나 다른언어로 배우는 알고리즘/자료구조는...글쎄요...
와우 학교에서 배웠던 정리 안된 지식들이 이 영상으로 한번에 싹 정리되었어요! 감사합니다. 너무 많은걸 배워서 도대체 뭐가 중요한지, 왜 배우는건지 포인트를 못 잡고 있었거든요. 이제 좀 정리가 되었으니 기억도 잘 할 수 있을 것 같습니다. 노마드 코더 진짜 좋아요 ㅋㅋ
This is exactly the video i was looking for when I heard of Time Complexity. I assume space complexity is the same as you describe with storage or required memory resources per input. Your videos are great thank you!
O(1), O(2) 를 나누지 않는 이유는 입력의 크기에 따른 변화가 없기 때문일 것 같아요. 그래도 정교하게 성능을 고민하는 사람들에게는 그런 것도 고민해볼만한 것이지만요. 고등학생보다 어린 친구들을 위해서 logarithm 까지 친절하게 설명해주신 것 같은데 감사합니다.
비행기에 실을 수 있는 데이터의 양이 무한이 아니므로 비행기 전송도 엄밀히 말하면 O(n) 이 맞지 않을까요?... 만일 비행기에 실을 수 있는 데이터의 양이 무한이라고 가정을 하면 공정하게 인터넷 대역폭도 무한이라고 가정을 해야 하고 그러면 둘 다 O(1)이 되겠죠...
@@cheong0813 비행기 수가 충분히 많으면 가능합니다. 만약 데이터를 하드디스크에 담고도 너무 많아서 비행기를 3대를 띄워야 한다면 3대를 동시에 띄우면 1대가 운행하는 시간과 똑같기 때문입니다. 반면에 인터넷을 이용한 전송은 데이터가 클수록 전송하는 시간이 많이 걸리기 때문에 위에 제시된 값이 맞습니다. 실제로 천문학에서 블랙홀의 형상을 발견하기 위해 우주의 사진을 셀 수 없이 많이 찍었는데, 이를 분석하기 위해 인터넷으로 자료를 전송하는 것이 아닌, 비행기로 날랐다고 합니다.
강의 좋네요. 저도 계산기프로그램 만들어 보면서 알고리즘의 중요성을 몸소 체험해보고 아 알고리즘이 매우 중요하구나 하고 느낀 경험이 있습니다. 저같은 경우는 Big(n)을 Big(log N)으로 개선해서 속도를 향상시킨 경험을 해봤습니다.주로 엔진을 만드는 개발을 하는데 알고리즘의 역할은 매우 중요할 수도 있다는 생각을 해 봤습니다. 일반 개발에서는 사용하는 프레이워크나 라이브러리에 이미 알고리즘이 녹아들어가 있어서 툴 사용법만 잘 알면 굳이 알고리즘 몰라도 별 문제가 없게 느껴질 수도 있지만요.