DSA 및 Big O 표기법 소개

DSA 마스터 참고사항:

Master DSA는 S/w Ers에게 높은 급여를 받을 수 있는 자격이 있습니다.
DSA는 소프트웨어 엔지니어링의 주요 부분입니다.
코드를 작성하기 전에 더 큰 그림을 이해하고 세부 사항을 자세히 살펴보세요.
DSA는 언어에 구애받지 않으므로 개념을 시각적으로 이해한 다음 l/g를 통해 해당 개념을 코드로 변환하는 것이 전부입니다.
앞으로 나올 모든 컨셉은 어떻게든 이전 컨셉과 연결되어 있습니다. 그러므로 연습을 통해 개념을 완전히 익히지 않은 이상 주제를 바꾸거나 앞으로 나아가지 마세요.
개념을 시각적으로 학습하면 자료에 대한 더 깊은 이해를 얻게 되어 지식을 더 오랫동안 유지하는 데 도움이 됩니다.
이 조언을 따르면 잃을 것이 없습니다.

Linear DS:
Arrays
LinkedList(LL) & Doubly LL (DLL)
Stack
Queue & Circular Queue

Non-linear DS:
Trees
Graphs

빅오 표기법

알고 성능 비교를 위해서는 이 표기법을 이해하는 것이 필수적입니다.
알고의 효율성을 비교하는 수학적 방법입니다.

시간 복잡도

코드 실행 속도가 빠를수록 코드는 낮아집니다
V. 대부분의 인터뷰에 임팩트가 있습니다.

공간 복잡도

저장 비용이 낮아 시간 복잡도에 비해 거의 고려되지 않습니다.
면접관이 이런 질문을 할 수도 있으니 이해가 필요합니다.

세 개의 그리스 문자:

1. 오메가
2. 세타
3. Omicron, 즉 Big-O [가장 자주 보임]

알고 사례

1. 최고의 사례 [오메가를 사용하여 표현됨]
2. 평균 사례 [Theta를 사용하여 표현됨]
3. 최악의 경우 [Omicron으로 표현]

기술적으로 평균 Big-O의 최상의 사례는 없습니다. 각각 오메가와 세타를 사용하여 표시됩니다.
우리는 항상 최악의 경우를 측정하고 있습니다.

## O(n): Efficient Code
Proportional
Its simplified by dropping the constant values.
An operation happens 'n' times, where n is passed as an argument as shown below.
Always going to be a straight line having slope 1, as no of operations is proportional to n.
X axis - value of n.
Y axis - no of operations 

// O(n)
function printItems(n){
  for(let i=1; i





<pre class="brush:php;toolbar:false">## O(n^2):
Nested loops.
No of items which are output in this case are n*n for a 'n' input.
function printItems(n){
  for(let i=0; i<n i console.log for j="0;" printitems>





<pre class="brush:php;toolbar:false">## O(n^3):
No of items which are output in this case are n*n*n for a 'n' input.
// O(n*n*n)
function printItems(n){
  for(let i=0; i<n i console.log iteration for j="0;" mid k="0;" inner printitems comparison of time complexity: o> O(n*n)


## Drop non-dominants:
function xxx(){
  // O(n*n)
  Nested for loop

  // O(n)
  Single for loop
}
Complexity for the below code will O(n*n) + O(n) 
By dropping non-dominants, it will become O(n*n) 
As O(n) will be negligible as the n value grows. O(n*n) is dominant term, O(n) is non-dominnat term here.
</n>

## O(1):
Referred as Constant time i.e No of operations do not change as 'n' changes.
Single operation irrespective of no of operands.
MOST EFFICIENT. Nothing is more efficient than this. 
Its a flat line overlapping x-axis on graph.


// O(1)
function printItems(n){
  return n+n+n+n;
}
printItems(3);


## Comparison of Time Complexity:
O(1) > O(n) > O(n*n)

## O(log n)
Divide and conquer technique.
Partitioning into halves until goal is achieved.

log(base2) of 8 = 3 i.e we are basically saying 2 to what power is 8. That power denotes the no of operations to get to the result.

Also, to put it in another way we can say how many times we need to divide 8 into halves(this makes base 2 for logarithmic operation) to get to the single resulting target item which is 3.

Ex. Amazing application is say for a 1,000,000,000 array size, how many times we need to cut to get to the target item.
log(base 2) 1,000,000,000 = 31 times
i.e 2^31 will make us reach the target item.

Hence, if we do the search in linear fashion then we need to scan for billion items in the array.
But if we use divide & conquer approach, we can find it in just 31 steps.
This is the immense power of O(log n)

## Comparison of Time Complexity:
O(1) > O(log n) > O(n) > O(n*n)
Best is O(1) or O(log n)
Acceptable is O(n)

O(n log n) : 
Used in some sorting Algos.
Most efficient sorting algo we can make unless we are sorting only nums.

Tricky Interview Ques: Different Terms for Inputs.
function printItems(a,b){
  // O(a)
  for(let i=0; i<a i console.log o for j="0;" printitems we can have both variables equal to suppose a is and b then will be very different. hence it eventually what call it. similarly if these were nested loops become>





<pre class="brush:php;toolbar:false">## Arrays
No reindexing is required in arrays for push-pop operations. Hence both are O(1).
Adding-Removing from end in array is O(1)

Reindexing is required in arrays for shift-unshift operations. Hence, both are O(n) operations, where n is no of items in the array.
Adding-Removing from front in array is O(n)

Inserting anywhere in array except start and end positions:
myArr.splice(indexForOperation, itemsToBeRemoved, ContentTobeInsterted)
Remaining array after the items has to be reindexed.
Hence, it will be O(n) and not O(0.5 n) as Big-O always meassures worst case, and not avg case. 0.5 is constant, hence its droppped.
Same is applicable for removing an item from an array also as the items after it has to be reindexed.


Finding an item in an array:
if its by value: O(n)
if its by index: O(1)

Select a DS based on the use-case.
For index based, array will be a great choice.
If a lot of insertion-deletion is perform in the begin, then use some other DS as reindexing will make it slow.

n=100에 대한 시간 복잡도 비교:

O(1) = 1
O(로그 100) = 7
O(100) = 100
O(n^2) = 10,000

n=1000에 대한 시간 복잡도 비교:

O(1) = 1
O(로그 1000) = ~10
O(1000) = 1000
O(1000*1000) = 1,000,000

주로 다음 4가지에 중점을 둘 것입니다.
Big O(n*n): 중첩 루프
Big O(n): 비례
Big O(log n): 분할 및 정복
빅오(1): 상수

O(n!)은 고의로 나쁜 코드를 작성할 때 주로 발생합니다.
O(n*n)는 끔찍해요 알고
O(n log n)은 허용되며 특정 정렬 알고리즘에서 사용됩니다
O(n) : 가능
O(log n), O(1) : 최고

공간 복잡도는 모든 DS, 즉 O(n)에서 거의 동일합니다.
공간 복잡도는 정렬 알고리즘에 따라 O(n)에서 O(log n) 또는 O(1)까지 다양합니다

시간 복잡도는 알고에 따라 다릅니다

문자열과 같은 숫자 이외의 정렬에 가장 적합한 시간 복잡도는 Quick, Merge, Time, Heap 정렬에 있는 O(n log n)입니다.

학습 내용을 적용하는 가장 좋은 방법은 가능한 한 많이 코딩하는 것입니다.

각 DS의 장단점을 토대로 어떤 문제 설명에서 어떤 DS를 선택할지 선택합니다.

자세한 내용은 bigoheatsheet.com을 참조하세요

위 내용은 DSA 및 Big O 표기법 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!