[일반] 아니 소인수분해 시간복잡도 지수시간인거 알고있었는데

[해르마(setset321)]

잘 생각해보니까 O(√n) 아닌가 이런 생각이 들어서 찾아보니까

입력의 정의를 잘못알고있었노,,,

솔직히 나도 몰랐다 싶으면 개추박으셈 부끄러우니까

[EN_SA(encludingsalt)]

...?

[익명(apg2fwpfgsz5)]

비록 위키에 대문짝하게 적혀있지만 문자열의 길이로만 한정할건 아님 너가 처음 생각한 루트n쪽으로 접근하는게 맞다

[익명(apg2fwpfgsz5)]

특히 정수론으로 가면 n이 0이 될때까지 반복하는게 많은것도 그렇고, 비결정론적이거나 휴리스틱적인것도 계산할 수 있어야 하니 더더욱

[해르마(setset321)]

그럼 소인수분해가 다항시간 알고리즘이라는거야 아니면 보기에 따라서 다항시간일수 있고 지수시간일수 있다는거야?

[익명(apg2fwpfgsz5)]

저 위키 정의에서 입력의 '문자열의 길이'라고 표현한걸 문자열로만 한정하지말고, 그냥 입력이 가지는 논리적인 크기라고 생각하는게 더 맞는것 같음 예를들어 소인수분해 할때는 n 의 제곱근까지만 보니까 루트n이 나올 수 있는거고

[익명(apg2fwpfgsz5)]

소인수분해 시간복잡도는 뭔가 말하기 애매하네. 걘 사정이 많아서 나도 정리가 잘 안됨

[해르마(setset321)]

논리적인 크기면 비트수가 논리적인 크기 아닌가? 그래서 입력 문자열크기가 비트수의 정수배로 볼수있는거아님? 논리적 크기가 이게 아닌가?

[익명(apg2fwpfgsz5)]

수학에 뭔가 자신이 없어서 설명을 잘 못하겠음 미안
https://gall.dcinside.com/mgallery/board/view/?id=ps&no=40420
얘
같은 경우는 최종 시간복잡도가 O(N + log p + M log_p X) 인데,
log_p가 나온 이유가 N 혹은 K가 0이 될 때까지 루프 돌려서였음.
모듈러가 p고, 그 수 만큼 N이 나뉘어졌으니 log_p가 나온거고

[익명(apg2fwpfgsz5)]

그냥 주어진 n에 대해서 반복문이 몇 번 돌아가는지를 계산하는거 같기도 하고

[익명(221.141)]

아님

[익명(221.139)]

Linear sieve 있지 않남

[익명(14.32)]

그냥 영문판을 읽으셈

[익명(14.32)]

그리고 맥락에 따라 다르게 보면 되는게, 예를 들어 유클리드 호제법을 분석할 때는 실제로 비트 레벨로 따지기도 한다. 근데 문자열 알고리즘이면 문자열의 길이를 쓰겠지. 근데 자료구조에서는 노드나 엣지의 수만 따지기도 하는 거고. 정렬 알고리즘이면 정렬할 대상의 개수가 되겠지. 자연수 n에 대해 O(sqrt(n)) 번의 elementary operation을 거치면 소인수분해 결과물을 얻을 수 있다고 하면 이거 굳이 비트수까지 따져야하냐?

[익명(14.32)]

PS에서 유의미한 64비트 이내에서의 소인수분해 뿐만 아니라, SOTA 알고리즘에서도 자연수 N에 대해 어느정도의 복잡도가 나올 것이다 라고 맥락을 충분히 갖춰서 얘기함. 물론 여기에 N이 x비트라고 치고 대충 N=2^x 대입하면 exponential 하게 나오지. 결론은 맥락이 진짜 중요한 거다

[해르마(setset321)]

그니까 비트얘기를 한게 입력이 단순 숫자면 입력의 척도가 숫자의 크기냐 비트수냐인거지

[해르마(setset321)]

아 밑에꺼를 댓글쓰고 나서봄 그니까 맥락에 따라 달라진다는거지?

[해르마(setset321)]

그리고 영문판 위키피디아에서도 인수분해는 sub-exponential time라 나와있긴함 일단은

[익명(14.32)]

맥락이 중요한 이유는 factorization이 exponential하다고 말하면, 현대 암호와 관련된 맥락을 좀 아는 사람이면, 알아서 비트 수에 대해 exponential 하다고 알아듣는데 반해 일반적으로는 자연수 N에 대해 O(2^N) 꼴로 나타나는 알고리즘을 exponential 하다고 생각해서 그런 거다. Exponential 복잡도라고 하면 meet in the middle, Sum over Subsets, 같은 문제들을 먼저 떠올린다고

[익명(14.32)]

다시 Euclidean algorithm의 예시를 갖고오면, gcd(N,M)을 구하는 복잡도가 O(logN) 이라고 퉁치고 넘어가는 경우도 있다. 왜? N > M이면 어차피 swap 한 번 해주면 끝이니까. 근데 O(log(min(N,M)) 라고 써도 틀린 거는 아니지. 근데 여기서 다시 N비트로 표현 가능한 자연수 x, y에 대해 gcd(x,y)를 O(N)에 구할 수 있다고 할 수도 있다. 근데 이게 틀린 거냐? N비트라고 미리 말을 했으면 당연히 틀릴 수가 없는 거지.

[익명(apg2fwpfgsz5)]

슈벌 내가 표현 못한걸 존나 다 알고있네 그냥.. ㄳㄳ

[해르마(setset321)]

입력의 정의가 하나로 정해진게 아니라 뭐에 대해 얘기하고 싶은지에 따라 다르게 얘기할수 있다는건가? 어렵네 나중에 책으로 다시 봐야겠다