큰 O 복잡성이 내 프로그램에서 정확합니까?

큰 O에 대해 모두 배우고 있고 각 프로그램의 Big Complexity를 얻으려고합니다. 내 큰 복잡성이 올바른지 확인하고 싶습니다.큰 O 복잡성이 내 프로그램에서 정확합니까?

프로그램 1 :

1 단계 - 파일 O(n)에서 모든 단어를 읽기는, n은 단어 목록 2 단계의 크기 - 각 단어의 문자를 통해 루프와 (I 세부 사항에 가지 않을거야으로 조작 어떤이는) 그 단지 루프, 않습니다 - O(1)

전체는 HashMap에 삽입 - - m가 3 단계는 단어의 문자 수입니다 O(m)O(n + m)

프로그램을 2 : 단계 1 - 프로그램에 단어 전달 2 단계 - 해시 맵에서 단어 찾아보기 - O(1) 3 단계 - 각 단어의 문자를 반복하고 O(m)을 조작합니다. 여기서 m은 단어의 문자 수입니다. 4 단계 - 함수에 단어를 입력 - 나는 이것이 m 단어의 문자 수는 O(2^m),로 계산 5 단계 - 해시 맵 O(1)

O(2^m + m)

프로그램이 관여하지 않는 O (N)에서 다시 조회 단어 때문에 나는 해시 맵을 찾고있다. 전달 된 단어의 문자를 반복하는 유일한 복잡도

출처

2013-04-23 Decrypter

프로그램 1의 2 단계에서 사용자가 수행중인 작업을 고려하지 않은 것처럼 보입니다 각 단어의 모자 –

"oop through the characters"? 문자를 통해 객체 지향 프로그래밍? 문자를 통해 처리 ondulating ornithopers? –

오타가 수정되었습니다. – Decrypter

모든 단어의 모든 문자를 반복하는 것은 O (n * m)입니다. 여기서 n은 단어의 수이고 m은 단어의 최대 길이입니다.

해시 맵 삽입 및 조회는 기술적으로 O (n)입니다 (모든 요소가 동일한 값으로 해시 된 경우). 그러나 교수님이 O (1)라고 말씀 하셨다면

Google에서 도와 드릴 수 없습니다. 함수가 무엇인지 모른 채 "4 단계 - 단어를 함수에 입력하십시오."

출처

2013-04-23 21:58:52

정확합니다. - 4 단계의 Big O는 O (2^m)입니다. 아, 조회는 최악의 경우 여야합니다. 조회가 O (n)이어야합니다. – Decrypter

이것이 맞습니까? 프로그램 2 - O (2n + 2^m + m) = O (n + 2^m + m) – Decrypter

O (n + 2^m + m) m은 작은 경우 O (2^m)로, 가능하면 O (n * 2^m)까지 감소 할 것이다 –

큰 O 복잡성이 내 프로그램에서 정확합니까?

답변

관련 문제