Java에서 Big-O 표기법

Question

안녕 얘들 아 나에게 큰 표기법을 설명 할 수 있습니까?

Answer 1

1- (필요 다른 추천 링크리스트에 하나의 셀로부터 이동 없습니다) 그래서 기본적 배열 [28] O 인 (1)

2- 두 개의 비교를 말할 수 배열 목록은 a와 함께 할 수있는 방식으로 수행 할 수 있습니다 낮은 O를 정렬하지만.

mergesort 또는 quicksort O (nlg (n))를 사용하여 각 arraylist를 정렬 한 다음 O (n)의 두 정렬 된 목록을 비교할 수 있습니다. 결과는 O (nlgn)입니다.

그러나 다른 알고리즘 (정렬 없음)은 한 배열 (n)의 각 요소를 반복합니다. 그리고 요소가 다른 배열 (n)인지 확인합니다 (중복을 올바르게 처리하도록 표시합니다). 이 후자의 알고리즘은 O (n^2)입니다.

3 예. 원하는 요소를 찾을 때까지 하나씩 전체 목록을 검토해야합니다.

Answer 2

배열을 가지고 있기 때문에 인접한 메모리를 의미합니다. 이는 연결된 목록 에서처럼 반복 할 필요가 없기 때문에 주어진 색인을 조회하는 것이 하나의 작업에 포함된다는 것을 의미합니다. 그래서 그것은 O (1)입니다.

ArrayList A의 각 요소는 B의 각 요소와 비교되어야하기 때문에 순서 나 정렬없이 두 개의 ArrayList 개체를 비교하면 O (n^2)가됩니다. 따라서 A에 n 개의 요소가 있고 B. 그러면 A와 B가 n 개의 비교를 요구하는 모든 원소가 생길 것입니다. A에 n 개의 원소가 있기 때문에 n 번 n 번 비교하면 O (n^2)가됩니다.

정렬 알고리즘을 사용한 경우 사용 된 정렬 알고리즘에 따라 O (n log n) 시간이나 O (n)과 같은 정렬 알고리즘만큼 빠릅니다.

정렬되지 않은 배열에서 특정 대상 값을 찾는 것은 실제로 O (n)입니다. 배열에있는 모든 요소를 ​​검색하여 존재하는지 확인해야하기 때문에 이러한 경우입니다. 목록에 n 개의 요소가 있으므로 n 개의 비교가 있음을 의미합니다. 어레이 요소는 무작위로 액세스 될 수 있기 때문에