오늘날의 가장 중요한 ISA 부서의 Big-O는 무엇입니까? 어떤 종류의 최적화가 있습니까? 아니면 순진한 O (분자/분모)입니까? modulus 연산에 많이 의존하는 코드를 작성하고 있습니다.부서 중 Big-O
예를 들어 10/5 및 20/5 및 40/5를 수행하는 데 걸리는 상대 시간은 얼마입니까? 인텔, nVidia, Qualcomm 등의 최신 프로세서는 부서별 Big-O가 동일합니까?
참고 : 여기서 나눗셈은 O (분자 크기)라고 가정하면 틀릴 수 있습니다.이 질문은 전혀 이해가되지 않을 수 있습니다. 이 경우에 나를 교정하십시오.
이 질문은 좋지 않습니다. 그러나 그것은 또한 "어리석은"것이 아니기 때문에 몇 가지 점에 대해 대답/명확히하려고 노력합니다.
거의 모든 최신 CPU/GPU에는 나누기 명령이 있습니다. 기본 단어 크기에서 작동하므로 Big-O의 경우 얼마나 빠릅니까 일정하지 않으므로 항상 O (1)입니다. 임베디드 프로세서, 마이크로 컨트롤러 및 이와 유사하게 구분 명령이없는 경우에도 소프트웨어에서 에뮬레이션되고 소프트웨어 에뮬레이션이 단어의 크기로 묶여 있기 때문에 항상 똑같은 시간을 수행 할 수 있습니다. 작동 (즉 O (1)도 의미 함).
단어가 아닌 크기의 데이터에 대해 수행 된 작업에 대한 예외는 예외입니다. 예 : BigInt 라이브러리에 대해 이야기 할 때. 그러나이 경우 모든 연산 (더하기, 곱하기, ...)은 더 이상 O (1)이 아니며 숫자의 크기에 따라 달라집니다.
그러나주의 : Big-O는 실제 계산 시간에 대해서는 말하지 않습니다. 그것의 단지 점근선적인 행동은 상수 요인을 무시합니다. 즉, O (n)을 사용하는 두 개의 알고리즘을 사용하는 경우에도 시차는 1000 배 (또는 원하는만큼)가 될 수 있습니다. 가장 좋은 예는 다음과 같습니다. 덧셈은 둘 다 O (1)이지만, 보통 나눗셈은 덧셈보다 실행하는데 훨씬 더 많은 사이클/시간이 걸린다.
자바는 어떨까요? 32 비트 시스템에서는 워드 크기의 두 배가됩니다. 아직 O (1) 런타임이 있습니까? – user1210233
64 비트 div 명령어가없는 경우에도 32 비트 명령어를 사용하여 64 비트 div를 에뮬레이트하거나 수행하려면 항상 일정한 수의 연산이되므로 O (1)이됩니다. 그러나 다시 : O 클래스는 동일하지만 실제 실행 시간의 차이는 약 3-6의 요소입니다 (단지 추측, 더 높거나 낮을 수 있음, 사용 된 플랫폼/시스템에 크게 의존 함). – flolo
또한 상각 된 복잡성에 대해 언급해야합니다. 나는 다른 작업에 대해서는 모른다. 그러나 추가는 O (1)로 상각된다. –
정수 나누기의 경우 일반적으로 일정하지만 지연 시간이 길어집니다. –
나는 모든 수학 연산이 1의 big-O를 갖는다 고 생각한다. –
또한 사용 된 나눗셈 알고리즘에 의존하지 않는가? http://en.wikipedia.org/wiki/Division_%28electronics%29 –