[2021/08/04][짤막한 이야기 - 시간 복잡도]

[2021/08/04][짤막한 이야기 - 시간 복잡도]
“시간 복잡도(Time-Complexity)”란 어떠한 일을 수행하는데 소요되는 대략적인 시간을 의미한다.
그림에는 특정 자료구조(Data Structure, 이 경우에는 배열)에 데이터가 입력되어 있다.
위의 자료구조에는 10개의 데이터가 무작위로 입력되어 있고, 아래의 자료구조에는 10개의 데이터가 정렬된 상태로 입력되어 있다.
위의 자료구조에서 가장 큰 값(9)을 찾기 위해서는 배열을 순차적으로 탐색하게 된다.
최악의 경우 가장 큰 값이 자료구조 내 가장 뒤에 있는 경우 10개의 데이터를 모두 탐색한 후에야 찾을 수 있다.
데이터가 10개가 아닌 1,000,000개(1백만개)라면 그만큼 시간이 더 소요된다. 즉, 데이터의 개수 N만큼 시간이 소요된다.
만약 배열이 정렬된 상태라면 데이터 개수 N이 100,000,000개(1억개)라고 하더라도 배열 제일 뒤만 확인하면 되기 때문에 데이터의 개수와 무관하게 1만큼 시간이 소요된다.
이를 각각 최악의 시간 복잡도를 표기하는 빅오(Big-O) 표기법으로 표현할 수 있으며 O(N)과 O(1)이라고 표기할 수 있다.
그리고 요즘 추세에 따르면 1억번의 연산을 수행하는데 1초가 걸린다고 가정한다.
그렇다면, 그림의 두 자료구조에서 A + B = 10인 두 수 A와 B를 찾는 시간 복잡도는 각각 얼마가 될까?
#이야기 #루니프 #알고리즘 #시간복잡도 #빅오

[2021/08/04][Short Story - Time-Complexity]
"Time-Complexity" means the approximate amount of time it takes to perform a task.
In the figure, data is entered into a particular data structure (in this case, an array).
The data structure above contains 10 data randomly, and the data structure below contains 10 data sorted.
In order to find the largest value (9) in the data structure above, an array is explored sequentially.
In the worst-case scenario, if the largest value is at the back of the data structure, it can only be found after exploring all 10 data.
If there are 1,000,000 (1 million) data, not 10 data, it takes that much more time. That is, it takes as much time as the number of data N.
If the array is aligned, even if the number of data N is 100,000,000 (100 million), it takes as much time as one, regardless of the number of data, since only the last part of the array needs to be checked.
This can be expressed in Big-O notation, which represents the worst-case time complexity, respectively, and as O(N) and O(1).
And current trends assume that it takes one second to perform 100 million operations.
So, what is the time complexity of finding two numbers A and B, which are A + B = 10, in the two data structures of the figure?
#Story #LootNiP #Algorithm #TimeComplexity #BigO