피보나치 이진수(이진수에서 연속된 숫자는 없음) - O(1) 방법

Fibbinary Numbers는 이진 표현에서 연속된 1이 없는 숫자입니다. 그러나 이진 표현에서는 연속된 0을 가질 수 있습니다. 이진수 표현은 1과 0의 두 자리 숫자만으로 2진수를 사용하여 숫자를 표시하는 표현입니다. 여기서는 숫자가 주어지고 주어진 숫자가 2진수인지 확인해야 합니다.

으아아아

설명 - 주어진 숫자 10의 이진수 표현은 1010이며, 이는 이진수 형태로 연속된 숫자가 없음을 나타냅니다.

으아아아

설명 − 주어진 숫자의 이진수 표현은 1100입니다. 이는 이진수 형식에 두 개의 연속된 1이 있음을 나타냅니다.

Naive Approach

의 중국어 번역은

Naive Approach

입니다.

이 방법에서는 분할 방법을 사용하여 각 비트를 찾고 필요한 정보를 얻기 위해 2로 나누어 이전 비트를 저장합니다. 현재 숫자가 0이 될 때까지 while 루프를 사용합니다.

이전에 찾은 비트를 저장하기 위한 변수를 생성하고 0으로 초기화하겠습니다. 현재 비트와 이전 비트가 모두 1이면 false가 반환되고, 그렇지 않으면 루프가 완료될 때까지 반복됩니다.

루프를 완료한 후 연속된 1이 발견되지 않았으므로 true를 반환합니다. 코드를 살펴보겠습니다 −

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 현재 숫자가 0이 될 때까지 2로 나누기 때문에 O(log(N))입니다.

위 코드의 공간 복잡도는 O(1)입니다. 여기서는 추가 공간을 사용하지 않기 때문입니다.

효율적인 방법

이전 방법에서는 각 비트를 하나씩 확인했지만 이 문제를 해결하는 또 다른 방법이 있는데, 바로 비트 이동입니다. 우리가 알고 있듯이 Fibbinary 숫자에서는 연속된 두 비트가 동시에 1이 되지 않습니다. 즉, 모든 비트를 왼쪽으로 한 비트씩 이동하면 이전 숫자와 현재 숫자의 비트가 각각 1이 됩니다. 입장은 결코 같지 않을 것이다.

예를 들어

주어진 숫자를 10으로 취하면 이진 형식은 01010이 됩니다. 비트를 1비트 이동하면 숫자 10100이 됩니다. 두 숫자 모두 같은 위치에 1비트가 없다는 것을 알 수 있습니다.

이것은 피보나치 이진수의 속성입니다. 숫자 n과 왼쪽 시프트 n의 경우 비트가 동일하지 않아 비트 AND 연산자가 0이 됩니다.

으아아아

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 모든 연산이 비트 수준에서 이루어지고 연산이 2개만 있으므로 O(1)입니다.

위 코드의 공간 복잡도는 O(1)입니다. 여기서는 추가 공간을 사용하지 않기 때문입니다.

결론

이 튜토리얼에서 Fibbinary 숫자는 이진 표현에서 연속적인 숫자가 없는 숫자라는 것을 확인했습니다. 그러나 이진 표현에서는 연속된 0을 가질 수 있습니다. 여기서는 두 가지 방법을 구현했는데, 하나는 시간 복잡도가 O(log(N))이고 공간 복잡도가 O(1)인 2로 나누기 방법을 사용하는 것이고, 다른 하나는 왼쪽 시프트와 비트 단위를 사용하는 것입니다. AND 연산자의

위 내용은 피보나치 이진수(이진수에서 연속된 숫자는 없음) - O(1) 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!