점근 표기법 복잡도는 다음 동작을위한 큰 O 표기법 무엇

-6

A = 1 * (1 0 1 0) + 0 * (0 1 0 1)

은

감사합니다. OlivierLi. A = 1 * (0 1 1 0 1 0 0 0) + 0 * (1 0 0 0 0 1 0 1) + 1 * (1 1 0 0 1 1 0 0) + 0 * (1 0 1 0 1 0 1 0)이다. 그것은 또한 O (1)입니다. 보시다시피 이진 비트에 8 이진 비트를 네 번 곱한 것과 같습니다. 그것이 O (1)이라면, 친절하게도, 어떻게 증명할 수 있습니까? 잘 부탁드립니다.

출처

2014-02-17 Sam

더 자세히 알고 싶습니다. 이처럼 그것은 나에게 이해가되지 않는다. 작업은 항상 정확히 같은 시간이 걸릴 것입니다. – Nabla

왜 태그가 달린 Matlab입니까? – Dan

만약 내가 이것을 MATLAB에서한다면, Big O fir은 무엇입니까? – Sam

이것은 O (1)입니다.

입력에 전혀 의존하지 않으며 항상 상수입니다.

출처

2014-02-17 13:31:39 OlivierLi

그럼, 이것에 대해 제발 : – Sam

무엇에 대해? – OlivierLi

감사합니다 OlivierLi. A = 1 * (0 1 1 0 1 0 0 0) + 0 * (1 0 0 0 0 1 0 1) + 1 * (1 1 0 0 1 1 0 0) + 0 * (1 0 1 0 1 0 1 0)이다. 그것은 또한 O (1)입니다. 보시다시피 이진 비트에 8 이진 비트를 네 번 곱한 것과 같습니다. 그것이 O (1)이라면, 친절하게도, 어떻게 증명할 수 있습니까? 잘 부탁드립니다. – Sam

여기서 문제는 비트 수를 변수로 간주할지 상수로 간주하는지 여부입니다.

비트의 수 : 복잡성은 O (1)입니다. 왜냐하면 복잡성은 가능한 모든 입력 숫자에 대해 동일하기 때문입니다.

가변 개수의 비트 : 첫 번째 숫자의 각 비트에 대해 이동 된 두 번째 숫자를 더합니다. 임의의 긴 숫자를 갖는 덧셈이 복잡성 O (N)을 가질 수 있다고 가정하면, 최종 복잡도는 O (N^2)이며, 여기서 N은 비트의 수입니다.

출처

2014-02-17 14:40:00

@ user3319291 :이 질문을하지 않았습니다. _ 비트 수를 항상 일정하다고 말하면 어떻게됩니까? Big O는 O (1) ._입니다. 원하는 경우 댓글을 달아주세요 ... 또한이 변경의 승인을 위해 투표 한 유권자를 이해하지 못합니다 ... –

죄송합니다, 우리가 말하면 비트 수는 항상 일정하며 우리는 4 비트에 8 비트를 곱합니다. 이 경우 O가 무엇입니까? – Sam

@Sam V-X의 답변에이 사건에 대한 결과가 명확하게 나와 있습니다. – Nabla

점근 표기법 복잡도는 다음 동작을위한 큰 O 표기법 무엇

답변

관련 문제