[DSA] 1. Data Structures and Algorithms

 

TABLE OF CONTENTS

 

1. What is good code?

무엇이 좋은 코드일까? => 2가지 조건을 만족시키면 된다. 

바로 Readability와 Scalability이다. 

하지만 대부분의 경우 Speed와 Memory는 trade-off 관계이다. 하나를 최적화 시키면 다른 하나가 안좋아진다는 말이다. 

따라서 보통 Time Complexity를 최적화하는 경우에는 Space Complexity를 포기하고, HashSet이나 HashMap과 같은 추가적인 자료구조를 사용하면 되는 것이고, Space Complexity를 최적화 하는 방법은 Time Complexity를 포기하면 된다. 

 

2. Big O

그러면 Big O notation이란 무엇일까?

빅오란 결국 복잡도를 표기하는 방법이다. 이렇게 함으로서 Time Complexity와 Space Complexity를 알 수 있어 Scalability를 때려맞출 수 있게 되는 것이다. 

Scalability란 아래의 그림처럼 # of operations가 Elements당 얼마나 이루어지는 가이다. 즉, Scalability = As the input grows, how much the whole algorithms slows down. It is a language we use for talking about how long an algorithms takes to run regardless of the computer differences => Big O does not depend on the CPU spec

 

아래가 Big-O Complexity Chart인데 아래로 갈 수로 좋다. 

그러면 Big O를 만드는 방법에는 뭐가 있을까? 아래와 같이 하면 된다. 최악의 경우를 가정하고, 모든 상수는 제거하고 등등

 

 

[Reference]

1. https://www.geeksforgeeks.org/time-complexity-and-space-complexity/

Time Complexity and Space Complexity - GeeksforGeeks

2. https://medium.com/@DevChy/introduction-to-big-o-notation-time-and-space-complexity-f747ea5bca58

Introduction to BIG O Notation — Time and Space Complexity