# Big O
시간복잡도와 Big-O 표기법
알고리즘의 시간 복잡도 > 알고리즘 비교의 기준 : CPU 처리 시간! 소요시간 측정 성능 측정 시 입력을 통일시킴 최악의 입력 n개가 들어온다고 가정하고 측정 시간 복잡도(Time Complexity) 알고리즘의 수행시간 의미(시간 복잡도가 높다 -> 느린 알고리즘) 시간복잡도 계산 사칙연산, 읽고 쓰기, 검증 등 단순 코드 : 한 statement 당 1 조건문 : max((True일 경우 시간), (False일 경우 시간)) -> 최악으로 가정 반복문 Big-O 표기법 Big-O 표기법이란? > 1) 6n + 4 > > 2) 3n + 2 > > 3) 3n² + 6n + 1 1번과 2번은 2배 차이가 나지만 n이 무한대로 커진다면 차이가 무의미할 것이다. 입력이 무한대로 커진다고 가정하여 최고차항만 남기고 계수와 상수 제거한다. 정확한 수식을 구하는 것은 불필
[Algorithm] 공간 복잡도
공간 복잡도 이 전까지는 시간과 관련하여 알고리즘들이 얼마나 빠르게 실행하는지에대해 문제를 바라 보았다. 이걸 바로 시간 복잡도라고 한다. 이제는 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지 하는지에 대해서 알아보자. 여전히 Big O표기법을 사용할 수 있지만 이제는 공간, 사용되는 메모리에 주목 하겠다. 공간 복잡도는 입력 되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간을 의미한다. 기본적인 규칙 > Boolean, Number, undefined, null은 javascript에서 모두 불면의 공간이다. 입력 크기와 상관없이 숫자가 1이든 1000이든 모두 같은 공간이라고 여긴다. String은 O(n) 공간이 필요하다. 만약 n이 문자열의 길이라면, 50자가 입력되었다면 1자인 문자열보다 50배 더 많은 공간을 차지하게 된다. reference, array, object도 대부분 O(n)이다.
[Algorithm] Big O 표현식 단순화
Big O 표현식 단순화하기 Big O 표기법 단순화는 모든 연산자들을 다 세는 것이 힘들고 정확한 갯수는 별로 중요하지 않다. 전체적인 추세를 중요하게 여긴다는 것이다. 5n+2라는 식을 그냥 n으로 단순화 할 수있다. n이 커질수록 실행 시간도 비례하게 늘어나고 n * 2든, n * 9, n * 10, n * 100 크게 중요하지 않다 전부 n이다. 그래프에 선이 n의 값과 비례하다는 것이다. 이 식들을 단순화하기 위해 도움이될 규칙들에 대해서 알아보자. 단순화 규칙 가장 중요하게 생각하는 것은 반복해서 말하지만 큰 그림이다. 그렇기 때문에 상수는 중요하지 않다. O(2n)이 있다면 이걸 O(n)으로 단순하게 표기할 수 있다. O(500)이 있다면 이걸 그냥 O(1)이라고 한다. O(500)은 쉽게 말하면 연산 갯수가 어떤 상황이든 500개라는 말이기 때문이다. 그래프 선을 보면 납작하기 때문이다.(n의 갯수와 시간이 비례하지않다.) O
[TIL] 내배캠 사전캠프 7일차
Big O란? Big O 표기법은 퍼지(fuzzy) 계산을 공식적인 표현. 정식으로 입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식이다. Big O는 어떤 함수의 입력 값이 늘어나는 것과 함수 실행 시간이 변하는 관계를 의미한다. 즉, 입력의 크기와 실행시간의 관계를 말한다. 다른 내용에는 상관 하지 않고, 오로지 전반적인 추세(trends)에 주목 하는것이다. 첫번째 함수에서 N의 값이 늘어났지만, 실행 되는 시간에는 아무 영향을 받지 않는다. 두번째 함수는 실행 되는 시간
SW사관학교 정글7기 개발일지 (08/16)
백준 풀이 알고리즘 Time complexity Comparison Sorting Algorithm 비교를 통해 정렬하는 알고리즘의 통칭 버블정렬, 선택정렬, 삽입정렬, 병합 정렬, 퀵 정렬 등 한계점 비교를 통한 정렬을 구현하는 과정에서 시간복잡도는 O(nlogn)을 넘을 수 없다는 점이 증명되었다. 의사 결정 트리를 활용해보자. https://mathcenter.oxford.emory.edu/site/cs171/decisionTree/ 우리가 정렬을 구현할 때 모든 원소를 하나하나 비교하게 된다면 N!의 시간을 소요하게 된다. 의사 결정 트리에서 높이=h(의사결정 횟수) 라고 생각하면 리프 노드의 개수는 최대 2^h개 이다. 즉
[알고리즘] 시간복잡도와 공간복잡도, Big O
Why? > 자료구조와 알고리즘을 공부하면서 마주쳤던 복잡도.. "몰라도 문제 푸는 데 지장 없지!"라고 생각하며 애써 외면해 왔지만 문제를 푸는 과정에 많은 시간 초과를 겪으며, 복잡도를 이해할 필요성을 느꼈다. 복잡도(Complexity) >알고리즘의 성능 및 효율성을 나타내는 척도로 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)가 있다. 복잡도를 나타내는 방법으로 빅 오(O), 오메가(Ω), 세타(Θ)가 있으며, 주로 빅 오와 세타 표기법이 많이 사용된다. >코딩 문제를 풀면서 시간제한과 메모리 제한을 두는데, 시간에 해당하는 것이 시간복잡도, 메모리에 해당하는 것이 공간복잡도이다. 이 두 가지를 고려하여 문제를 풀어야 한다. 1️⃣ 시간복잡도(Time Complexity) >입력값
Big O
알고리즘 스피드의 표현법 알고리즘의 스피드는 완료까지 걸리는 절차의 수로 결정된다. 따라서 같은 작업을 수행하는데 5번 스텝만 필요한 알고리즘이 10개 스텝이 필요한 알고리즘 보다 훌륭한 알고리즘이다. 선형 알고리즘만 봐도 아이템이 10개인 경우 10번의 스텝이 필요하다. 따라서 input size 가 N 이라면 선형 알고리즘은 N 스텝이 요구된다고 할수 있다. 선형 검색의 시간복잡도는 O(N)을 갖는다고 할수 있다. 선형 검색 시간 복잡도 = O(N) Big O 는 큰 원리에만 관심이 있어 , 인풋 사이즈가 엄청나게 커져도 관계없이 미리 정해진 숫자에 따라 작동한다. 예) 항상 200개의 스텝이 필요한 함수가 있다면 인풋 사이즈와 관
[CS] 자료구조의 종류와 시간 복잡도
자료구조의 종류 사진출처 : A to Z : JavaScript 자료구조는 크게 3가지로 분류할 수 있음 단순 구조, 선형 구조, 비선형 구조 그 중에서도 선형과 비선형에 대해 간략하게 정리하겠음 선형 구조 : 한 원소 뒤에 반드시 하나의 원소만 존재하는 구조 (자료가 선형으로 존재하는 구조) Array, Linked List, stack, queue 해당 사진출처 : A to Z : JavaScript 비선형 구조 : 원소간 다대다 관계를 가지는 구조 (계층적 혹은 망형 구조) tree, graph 해당 
[JS]Big-O 표기법
배운 내용을 개인적으로 정리하는 블로그입니다. 틀린 내용이 있을 수 있으며 첨언은 언제나 감사합니다 :) Big-O 표기법 알고리즘이 얼마나 효율적인지 측정하는 함수(알고리즘이 최악의 경우에 걸리는 시간을 표기함) |O(n)|내용| |:---:|---| |O(1)|데이터량에 상관없이 연산시간 일정 |O(n)|데이터 량 비례해 일정하게 연상시간 증가 | |ex)순차탐색 |O(log n)|데이터량에 비해 초반엔 시간이 확 증가하다가, 데이터양이 많아질수록 확 줄어들음 | |ex)이진탐색 계산법 big-O 표기법의 계산법은 의외로 쉬운데, 가장 큰 항만 남겨놓고 앞뒤로 자른다! 필자의 경우 이를 고등학생때 배운 limit로 이해했다(틀렸다면 지적 부탁한다
[Algorithm] 시간복잡도(Time Complexity) - 알고리즘 선택의 기준
🤷🏻♀️ 시간복잡도(Time Complexity)란? 알고리즘에서 시간복잡도는 [ 주어진 문제를 해결하기 위한 연산 횟수 ] 를 의미합니다. 시간복잡도와 로직 수행 시간은 비례하므로 시간 복잡도 수치가 작을수록 효율적인 알고리즘임을 뜻합니다. 파이썬에서는 2000만 번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측 가능합니다. 📌 시간 복잡도 표기법( 점근 표기법 ) 빅 오메가(Big - Ω) [ best case ] 최선일 때의 연산횟수를 나타낸 표기법 빅 세타(Big - θ) [ average case ] 보통일 때의 연산횟수를 나타낸 표기법 빅
[알고리즘] 시간복잡도
알고리즘의 효율성 길이(개수)가 N인 데이터에 대한 연산의 횟수 점근 표기법 case에 따라 분류 best case 첫번째에 target값 존재 => 1번째만에 target값 찾음 worst case 마지막에 target값 존재 혹은 target값 없음 => N번째에 target값 찾음 or N번 다 돌고 못찾음 > lower bound, 점근표기법 Ω(1) Ω(N) = Big-Omega 표기법 알고리즘의 효율성을 하한선을 기준으로 설명 함수 실행시간은 아무리 빨라도 (상수) 시간 이상이다 > upper bound, 점근표기법 O(N) O(1) = Big-O 표기법 알고리즘의 효율성을 상한선을 기준으로 설명 함수 실행시간은 아무리 오래걸려도 N에 비례하는 정도 이하다 > tight bound, 점근표기법 Θ(N) Θ(N) = Big-theta 표기법 lower bound 와 upper
[python] in 시간복잡도
참고: python wiki https://wiki.python.org/moin/TimeComplexity in 연산의 시간복잡도가 궁금해서 찾아보게 되었다. in 연산의 시간복잡도 자료형에 따른 시간복잡도의 차이가 있다. |자료형|average|worse case| |---|---|---| |list|O(n)|O(n)| |tuple|O(n)|O(n)| |set|O(1)|O(n)| |dict|O(1)|O(n)| list와 tuple은 하나하나 순회하기 때문에 O(n) set과 dictionary는 내부적으로 hash를 이용해 저장하기에 O(n), 해시의 충돌이 많은 경우 O(1)이 된다.
[코딩테스트] 복잡도
개요 독학으로 코딩테스트를 준비하면서 제일 어려웠던 것은 문제에 적합한 알고리즘을 찾는 방법이었습니다. 자료를 찾던 중 복잡도에 대한 내용을 알게 되었고 이를 이용하여 적합한 알고리즘을 선택할 수 있다는 것을 알게 되었습니다. 이 글은 복잡도에 대해 간단하게 정리한 글입니다. 복잡도 (Complexity) 복잡도는 알고리즘의 성능을 알 수 있는 척도로 시간 복잡도(Time Complextiy)와 공간 복잡도(Space Complexity)로 나눌 수 있다. 시간 복잡도 (Time Complextiy) 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수 시간 복잡도는 특정한 크기(N)의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다. 시간 복잡도는 알고리즘이 동작하는 시간이 아니라 알고리즘이 동작하는 스텝의 개수로 생각한다. 이는 시간으로 계산할 경우 하드웨어의 성능에 따라 다르게 나타날 수 있기 때문이다. 공간 복잡도 (Space Com
[Python] 알고리즘 요구사항 분석 ⌘
⏱️ 시간 복잡도 (Time Complexity) > 단순하게 생각해서 '특정한 크기의 입력에 대한 알고리즘의 대략적인 수행 시간' 보통 코딩테스트 문제의 시간제한은 1초 ~ 5초 로 제한 Python 의 경우, 초당 약 20,000,000(2천만)번의 연산이 가능하다고 알아두자. Python 의 in 시간 복잡도는 자료형에 따라 다르다. List, Tuple : O(N) - 하나 하나 탐색! Set, Dictionary : O(1) ~ O(N) - Hash를 통해 저장하므로 접근 시간은 상수 시간! (단, Hash 의 충돌이 많아 성능이 떨어지는 경우 선형시간이 걸릴 수 있음.) 알고리즘의 따른 Big-O notation 은 다음과 같다. 
[알고리즘] 시간복잡도
시간복잡도 알고리즘 복잡도란? > 어느 알고리즘이 더 효율적인지를 분석하기 위한 기준 알고리즘 복잡도 종류 > 1. 시간복잡도 > 알고리즘의 실행 속도를 의미한다. 반복문이 중요하게 작용한다. 2. 공간복잡도 > 알고리즘이 사용하는 메모리의 사이즈를 의미한다. 메모리의 발달로 공간복잡도에 중요도가 시간복잡도에 의해서 줄어들고 있다. 알고리즘의 성능 표기법 1. Big-O (빅-오) 표기법 : O(N) > 알고리즘의 최악의 실행시간을 표기 일반적으로 사용하는 표기법 2. $$\Omega$$ 표기법 : $$\Omega$$(N) > 알고리즘의 최상의 실행시간을 표기 3. $$\Theta$$ 표기법 : $$\Theta$$(N) > 알고리즘의 평균 실행시간을 표기 Big-O 표기법 > O(입력) 입력 n에 따라 결정되는 시간복잡도 함수 $$O(1) < O(logn)
알고리즘 - 시간 복잡도) 복습을 위해 작성하는 글 2023-04-11
📒 갈무리 - 시간 복잡도(Time complexity) 📌 시간 복잡도란? - 알고리즘이 문제를 해결하는데 걸리는 시간(연산)의 횟수를 말한다. Big-Ω(빅 오메가) : 알고리즘의 최상의 실행 시간을 표기한다.(Best Case) Big-O(빅 오) : 알고리즘의 최악의 실행 시간을 표기한다.(Worst Case) Big-θ(빅 세타) : 알고리즘의 평균 실행 시간을 표기한다.(Average Case) - Best Case 또는 Average Case로 시간 복잡도를 구한다면 최악의경우 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하기 때문에 문제 해결에 필요한 시간이 많이 필요하게 된다. 그렇기 때문에 항상 최악의 경우도 고려하여 대비하는 것이 좋기 때문에 Big-O(빅 오) 표기법을 주로 사용한다.   📌 Big-O 표기법이란? - Big-O 알고리즘의 성능을 수학적으로 표현해주
2023 4 10
한 것 데이터 엔지니어링 데브코스 2주차 자료구조/알고리즘 풀기(1) 강의 코딩테스트와 코딩인터뷰 특강 velog 첫글 작성🙃(이 글) 배운 것 python3 list 객체의 매서드인 sort, python3 자체 내장함수인 sorted의 차이점과 인수, 활용법을 정확히 알게 되었다. (https://gist.github.com/sanso62/eed511f4b42c549a773e0ed70521937c) Big-O(logN) 에서 로그밑은 신경안써도 된다! worst case를 따지면, N을 무한히 큰 값으로 정의되므로 밑이 아무거나 와도 큰 상관이 없다. 지금까지 나는 2인줄 알았다. 물론 대부분의 알고리즘이 2이지만
[코테] 기초편 빅오 표기법(Big-O Notation)
1. 복잡도 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 간단히 2가지로 나뉜다. 시간 복잡도: 알고리즘을 동작하는 데에 필요한 연산의 횟수 공간 복잡도: 알고리즘의 동작에 필요한 메모리의 크기 1.1 시간 복잡도 출처:제로베이스 >코딩 테스트를 처음 접하게 되면 가장 당황하게 되는 것 중 하나가 'Time Limit Exceeded'로 시간 초과가 나며 오답처리 되는 경우다. 분명히 연습할 때 파이참이나 VS코드 등으로 연습할 때에는 답이 분명히 나왔는데 여러 사이트에서 실제 코딩 테스트 시험을 보게 되면 만나게 되는 오답 처리가 당황스럽다. 내가 작성한 코드의 연산 시행 횟수가 출제자가 의도한 풀이 시간을 넘겼기
자료구조 & 알고리즘 (1)
자료구조 자료구조(Data Structure)를 배워야 하는 이유 데이터의 형태와 쓰임에 가장 적합한 자료구조를 쓰는것이 매우 중요 컴퓨터의 자원은 한정적임 === 아무리 좋은 하드웨어를 사용하더라도 무제한이 되는건 아님 제한된 제약조건 내에 정확한 결과를 내야함 적합하지 않은 자료구조를 사용했을 때 느린 시스템 트래픽이 몰렸을 때 펑🤯🤯🤯🤯 결론 : 어떤 자료구조를 사용하는게 효율적인가, 자료구조의 동작원리를 아는것이 나중에 발생할 수 있는 문제를 예측할 수 있음 알고리즘 좋은 소프트웨어 란? 효율적이어야 함 적은 자원 사용 빠른 실행 시간 적은 비용으로 개발하고 유지보수할 수 있어야 함 알고리즘이란 어떤 문제가 주어졌을 때, 문제를 풀기위한 동작들의 절차 ex ) 라면 끓이는 법, 집에서 학교 가는 법, 네이버에 들어가는 법
알고리즘 정리1 : Big-O
Big-O 시간복잡도 빅오 표기법(big o Notation) 시간복잡도(time complexity) 공간복잡도(space complexity) 빅오 표기법을 이용하여 각기 다른 알고리즘들의 시간복잡도와 공간복잡도를 평가한다. 같은 문제를 해결하는 여러 방법이 있을때 각 방법 중 어느 것이 베스트인지를 어떻게 평가하나? 빅오의 목적 → 여러가지 코드를 비교하고 성능을 평가하기 위해 빅오 표기법은 알고리즘이나 함수의 수행 시간 복잡도를 표기하는 방법 중 하나. 입력값의 크기에 따른 알고리즘의 성능을 나타내며, 보통 최악의 경우 시간 복잡도를 나타낸다. 빅오 표기법은 다양한 형태가 있지만, 가장 일반적인 형태는 O(1), O(log n), O(n), O(n log n), O(n^2). 이를