Will it scale?

This age-old question is always asked during the design phase of software development and comes in several flavors. From an architectural standpoint, scalability is how easy it is to make changes to your app. From a database standpoint, scalability is about how long it takes to save or retrieve data to the database.

For algorithms, scalability refers to how the algorithm performs in terms of execution time and memory usage as the input size increases.

When you’re working with a small amount of data, an expensive algorithm may still feel fast. However, as the amount of data increases, an expensive algorithm becomes crippling. So how bad can it get? Understanding how to quantify this is an important skill for you to know.

In this chapter, you’ll take a look at the Big O notation for the different levels of scalability in two dimensions--execution time and memory usage.

확장이 가능 합니까?

이 오래된 질문은 소프트웨어 개발의 디자인 단계에서 항상 요구되며 여러 가지 특징이 있습니다. 아키텍처 관점에서 확장 성은 앱을 쉽게 변경하는 것입니다. 데이터베이스 관점에서 확장 성은 데이터를 데이터베이스에 저장하거나 검색하는 데 걸리는 시간에 관한 것입니다.

알고리즘의 경우 확장성은 입력 크기가 증가함에 따라 실행 시간 및 메모리 사용량 측면에서 알고리즘의 성능을 나타냅니다.

소량의 데이터로 작업 할 때 비싼(expensive) 알고리즘도 여젼히 빠르게 느껴질 수 있습니다. 그러나 데이터 양이 증가함에 따라 expensive한 알고리즘은 나빠질 수 있습니다. 얼마나 나빠질수 있을까요?

이를 정량화하는 방법을 이애하는 것은 중요한 기술 입니다.

이 장에서는 실행 시간과 메모리 사용이라는 두 가지 차원의 확장성 수준에 대한 Big O 표기법을 살펴 봅니다.

Time complexity - 시간 복잡도

For small amounts of data, even the most expensive algorithm can seem fast due to the speed of modern hardware. However, as data increases, cost of an expensive algorithm becomes increasingly apparent. Time complexity is a measure of the time required to run an algorithm as the input size increases. In this section, you’ll go through the most common time complexities and learn how to identify them.

소량의 데이터의 경우 최신 하드웨어의 속도로 인해 가장 비싼 알고리즘도 빠르게 보일 수 있습니다. 그러나 데이터가 증가함에 따라 값 비싼 알고리즘의 비용이 점점 뚜렷해 집니다.

시간 복잡도는 입력 크기가 증가함에 따라 알고리즘을 실행하는 데 필요한 시간을 측정 한 것입니다.

이 섹션에서는 가장 일반적인 시간 복잡성을 살펴보고 이를 식별하는 방법을 학습합니다.