이 이전 SO 포스트 .NET 교점을 이용하여 설명() 메소드시간/공간 복잡도() 메소드
Intersection of two sets in most optimized way
그것은 O로서 법의 큰 O 복잡도 설명 (m + n). 그것은 시간이 모두 및 공간에 대한 큰 O를 복잡 한가요?
또한 위의 복잡도가 o (n + m)로 작성되어야하므로 n은 큰 o 표기법에서 m 앞에 와야한다는 것을 읽었습니다. m 앞의 n은 적절한 순서인가, 또는 이러한 변수의 순서는 큰 o 표기법으로 (대단히) 중요하지 않습니까?
(1) 답변은 한 목록에서 해시 집합을 만들고 다른 목록의 요소를 확인하는 것에 대해 설명합니다. 공간의 복잡성은 해시 셋을 구축 할 때 발생합니다. 해시 세트의 크기는 해시 세트를 생성하는 콜렉션에 따라 m 또는 n 중 하나에 들어갈 요소의 수에 비례합니다. 최악의 경우 더 큰 세트에서 해시 세트를 빌드한다고 가정 해 봅시다. 그러면 공간 복잡도는 O (max (m, n))입니다. 이 복잡도 클래스는 O (m + n)과 동일합니다. 왜? 왜냐하면 max (m, n) < 1 * (m + n)에 대해 모든 양의 m, n; 모든 양의 m, n에 대해 m + n < = 2 * max (m, n). 그래서 예, 설명 된 방법의 시간과 공간의 복잡성은 모두 O (m + n) 또는 O (max (m, n))와 동일합니다.
(2) m + n < = 모든 양의 m, n에 대해 1 * (n + m) 및 모든 양의 m, n에 대해 n + m < = 1 * (m + n). 따라서, O (m + n)은 O (n + m)과 동일하다.
시간과 공간 모두에있어 큰 복잡성입니까?
O (m + n) 방식을 사용하는 경우 공간의 복잡도는 O (m < n ? m : n)가됩니다. 왜? 그 중 m과 n 중 더 작은 것을 메모리에 저장 한 다음 큰 것으로부터 한 번에 한 항목을 읽어 큰 것 중 한 항목이 더 작은 항목에 있는지 테스트 할 수 있습니다. 그렇지 않으면 두 가지를 모두 메모리에서 없애면 공간 복잡도는 O (1)이되고 시간 복잡도는 O (mn)로 줄어 듭니다.
올바른 순서 앞에 n 있습니까? 아니면 이러한 변수의 순서가 큰 o 표기법과 관련이 없습니까?
m + n = n + m이기 때문에 전혀 문제가되지 않습니다. 복잡성이 O (m Log n) 또는 O (mn)와 같으면 O (n Log m) 또는 O (nm)로 작성할 수 없습니다.