최근에 인터뷰에서 기술적 인 질문에서 제기 된 다양한 알고리즘의 Big-O와 관련된 몇 가지 질문을 받았습니다. 나는 이것에 대해 잘 수행하지 못했다고 생각합니다. 10 년 동안 알고리즘의 Big-O를 계산하도록 요청 받았던 프로그래밍 과정을봤을 때, 저는 'Big-O'에 대해 하나의 토론을하지 않았습니다. 나는 일하거나 디자인했다. 저는 다른 팀원들과 많은 토론에 참여해 왔으며 코드의 복잡성과 속도에 관해 함께 연구 한 건축가들과 함께 해왔지만 실제 프로젝트에서 Big-O 계산을 실제로 사용한 팀은 본 적이 없습니다. 토론은 항상 "아웃 데이터에 대한 우리의 이해를 고려해 볼 때 더 효과적이고 효율적인 방법이 있습니까?" 절대로 "이 알고리즘의 복잡성은 무엇입니까?"'현실 세계'에서 Big-O 복잡성 평가를 사용합니까?
사람들이 실제로 코드에서 "Big-O"에 대한 토론을 실제로했는지 궁금합니다.
너무 많은 것을 사용하지 않으므로 그 의미를 더 잘 이해할 수 있습니다.
O (N^2) 정렬 알고리즘 사용의 결과를 알지 못하는 프로그래머가 있습니다.
나는 학계에서 일하는 사람들과는 별개로 매일 분노로 Big-O Complexity Analysis를 사용할 것입니다.
Big-O 표기법은 다소 이론적 인 반면, 실제로는 실제 프로파일 링 결과에 더 많은 관심을 가지고 있습니다. 실제 프로파일 링 결과는 성능이 얼마나 어려운지를 보여줍니다.
도서별로 O(n^2)과 O(nlogn)의 상한이있는 정렬 알고리즘이 두 개있을 수 있지만 프로파일 링 결과에 더 효율적인 오버 헤드가있을 수 있습니다 (이론적으로 발견 된 바운드에 반영되지 않음). 이론적으로 덜 효율적인 정렬 알고리즘을 선택할 수 있습니다.
결론 : 실생활에서 프로파일 링 결과는 일반적으로 이론적 인 런타임 경계보다 우선합니다.
그런 경우 실제 데이터로 프로파일 링하는 데주의하십시오. 지수 런타임을 사용하는 알고리즘은 작은 데이터 집합에 대해서는 정상적으로 실행되고 특정 경계를지나 치명적으로 실패 할 수 있습니다. 그것들은 사전 분석을 통해 잡을 수있는 것들이지만, 당신이 얼마나 정확하게 프로파일 링 했는가에 따라 프로파일 링만으로는 탐지하기 어려울 수 있습니다. – Joey
@Johannes - 실생활에서는 단순히 Big-O 표기법에 반영되지 않은 특정 완화 및 가정을 허용합니다. –
사과와 오렌지를 비교하고 있습니다. 프로파일 링은 알고리즘이 * 지금 * 수행하는 방법을 알려줍니다. Big-O 표기법은 입력 크기가 커지면 확장 방법을 알려줍니다. 프로파일 링이 순진하고 나쁘게 역효과를 낼 수 있다고 말하면서 프로파일 링을 신뢰합니다. 앞으로 더 큰 문제의 크기를 다루어야 할 것으로 예상된다면, 빅 - 오 복잡성에 대해 거의 알고 있어야합니다. 프로파일은 "우선 순위"를 갖지 않으며 완전히 다른 것을 알려줍니다. 둘 다 해결하려는 상황에서 가치가 있습니다. – jalf
내 개인적인 경험에 대한 대답은 - 아니요. 아마 이유는 간단하고 잘 이해 된 알고리즘과 데이터 구조 만 사용하기 때문입니다. 그들의 복잡성 분석은 이미 수십 년 전에 완성되어 발표되었습니다. 멋진 알고리즘을 피하는 이유는 Rob Pike here입니다. 요약하면, 종사자는 새로운 알고리즘을 발명 할 필요가 거의 없으며 결과적으로 Big-O를 거의 사용하지 않아도됩니다.
그렇다고 빅 오에 능숙하지 않아야한다는 의미는 아닙니다. 프로젝트는 완전히 새로운 알고리즘의 설계와 분석을 요구할 수 있습니다. 실세계의 예를 보려면 Skiena의 The Algorithm Design Manual에서 "전쟁 이야기"를 읽어보십시오.
나는 항상 그렇다. 필자의 경우 일반적으로 사용자, 데이터베이스의 행, 프로모션 코드 등 "큰"숫자를 처리해야 할 때 알고리즘의 Big-O를 알아야하고이를 고려해야합니다.
예를 들어, 배포 용 임의의 프로모션 코드를 생성하는 알고리즘을 사용하여 수십억 개의 코드를 생성 할 수 있습니다. O (N^2) 알고리즘을 사용하여 고유 한 코드를 생성하는 것은 CPU 시간을 몇 주간을 의미하지만 O N) 시간을 의미합니다.
또 다른 전형적인 예는 코드의 검색어입니다 (좋지 않음). 사람들은 테이블을 검색 한 다음 각 행에 대해 쿼리를 수행합니다. 그러면 N^2에 대한 순서가 표시됩니다. 일반적으로 SQL을 올바르게 사용하도록 코드를 변경하고 N 또는 NlogN을 주문할 수 있습니다.
제 경험상 프로파일 링은 올바른 알고리즘 클래스가 사용 된 후에 만 유용합니다. 프로파일 링을 사용하여 "작은"숫자로 묶인 응용 프로그램이 왜 성능이 좋지 않은지 이해하는 것과 같은 나쁜 행동을 포착합니다.
없음 불필요한의 N 제곱 내 경험에
당신은 그것을 논의가 필요하지 않기 때문에, 그것에 대해 많은 토론을하지 않습니다. 실제로, 내 경험상, 일어난 모든 일은 느린 것을 발견하고 실제로 O (n log n) 또는 O (n) 일 수있는 경우 O (n^2) 인 것을 확인한 후 이동합니다. 그것을 바꿔라. "그게 제곱인데, 고쳐라."이외의 논의는 없다.
네, 제 경험상 꽤 많이 사용하지만, "다항식의 차수를 줄이십시오"라는 기본 감각으로 "예"에 대한 약간의 고도로 조정 된 분석이 아니라, 미친 알고리즘, 우리는 logN에서 Ackerman의 함수의 역수로 증가 할 것입니다 "또는 그런 말도 안되는 것. 다항식보다 적은 것, 그리고 이론은 창 밖으로 나가고 프로파일 링으로 전환합니다 (예 : O (n)과 O (n log n) 사이에서 결정, 실제 데이터 측정).
나는 정신을 살리기 위해 logN을 유지할 것입니다. – quasiverse
아니요. 실제 상황에서는 Big-O 복잡성을 사용하지 않습니다. (아마 잘못 ..하지만 내 걸릴.)
큰-O 복잡성 물건은 궁극적으로 알고리즘이 얼마나 효율적으로 이해하는 것입니다 -
전체 문제에 대한 내보기
이있다. 경험이나 다른 방법을 통해 다루는 알고리즘을 이해하고 적절한 장소에서 올바른 골치 거리를 사용할 수 있다면 중요한 점이 있습니다.당신이이 빅 오 물건을 알고 제대로, 잘 사용할 수 있다면.
만약 당신이 알 고스와 그 효율성을 수학적 방법으로 이야기하는 것을 모른다면 - 빅 - 오 물건이지만, 정말로 중요한 - 상황에서 사용하기에 가장 좋은 알 고를 - 당신은 완벽하게 괜찮습니다.
나도 몰라요.
3 중첩 된 for -loops가 중첩 된 for -loop보다 나쁘다는 것을 알고있는 정도까지. 다른 말로 표현하자면, 나는 그것을 기준 직감으로 사용한다.
저는 학계 밖에서 알고리즘의 Big-O를 계산 한 적이 없습니다. 만약 내가 어떤 문제에 접근하는 두 가지 방법이 있다면, 내 직감에 다른 하나보다 Big-O가 낮을 것이라고 말하면, 더 이상 분석하지 않고 본능적으로 작은 것을 가져갈 것입니다. 나는 특정 내 알고리즘에 제공 N의 크기 알고, 나는 그것이 (100 개 요소에서 말) 상대적으로 작은 것으로 특정에 대한 을 알고 있다면, 다른 한편으로
, 나는 수도 가장 읽기 쉬운 코드를 사용하십시오 (필자가 작성한 지 한 달 후에 코드가 무엇을하는지 알고 싶습니다). 결국, 100^2와 100^3 실행의 차이는 오늘날의 컴퓨터를 사용하는 사용자에게는 거의 눈에 띄지 않습니다 (달리 입증 될 때까지).
그러나 다른 사람들이 지적했듯이 프로파일 러에는 마지막으로 명확한 단어가 있습니다. 필자가 작성한 코드가 느리게 실행되면 프로파일 러를 이론적 인 규칙보다 더 신뢰하고 이에 따라 수정합니다.
프로필 링 데이터가 필요할 때까지 최적화를 보류하려고합니다.물론 설계 시간에 하나의 알고리즘이 다른 옵션보다 더 효율적일 것이라는 점이 분명하지 않다면 (프로젝트에 너무 많은 복잡성을 가하지 않고).
코드 조각에 대한 심층적 인 분석은 거의 필요하지 않지만 중요한 의미를 알고 작성한 코드의 복잡성과 그것이 가져올 결과를 신속하게 평가할 수 있어야합니다 .
개발 단계에서는 종종 "충분 함"이라고 느끼는 경우가 많습니다. 어, 아무도이 배열에 100 개 이상의 요소를 넣을 수 없습니까? 그런 다음 어느 날 누군가가 배열에 1000 개의 요소를 넣을 것입니다 (코드를 허용하면 그 중 하나를 사용합니다). 그리고 지금 충분히 좋은 n^2 알고리즘은 큰 성능 문제입니다.
다른 방법으로는 유용 할 수 있습니다. 기능적으로 n^2 개의 연산을 수행해야하며 알고리즘의 복잡도가 n^3 인 경우,이를 수행하기 위해 수행 할 수있는 작업이있을 수 있습니다 n^2. n^2이면 좀 더 작은 최적화 작업을해야합니다.
반대로 정렬 알고리즘을 작성하고 선형 복잡성을 발견하면 문제가 있다는 것을 확신 할 수 있습니다. (물론, 실생활에서, 당신은 당신 자신의 정렬 알고리즘을 작성해야하는 경우는 드뭅니다. 그러나 한 번 인터뷰에서 자신의 단 하나의 루프 분류 알고리즘에 만족하는 사람을 보았습니다.).
예, 사용합니다. 그리고 "orderCount"또는 "xyz"가 더 나은 변수 이름인지 자주 논의하지 않는 것처럼 자주 논의되지 않습니다.
일반적으로, 당신은 앉아서하지 않고 는에게 그것을 분석,하지만 당신은 당신이 알고있는 것을 기반으로 직감을 개발하고, 거의 대부분의 경우에 즉시에 O -complexity을 추정 할 수있다.
많은 목록 작업을 수행해야 할 때 대개 나는 생각합니다. 나는 불필요한 O(n^2) 작업을하고 있는데, 그것은 선형 시간에 수행되었을 수 있습니까? 목록을 몇 번 지나가고 있습니까? 공식 분석을하기 위해 필요한 것은 아니지만 big-O 표기법에 대한 지식이 없으면 정확하게 수행하는 것이 더 어려워집니다.
소프트웨어가 더 큰 입력 크기로 수용 가능하게 수행되게하려면 정식 또는 비공식적으로 알고리즘의 big-O 복잡성을 고려해야합니다. 프로파일 링은 프로그램이 어떻게 을 수행하는지 알려주는데 유용하지만, O(2^n) 알고리즘을 사용하는 경우 프로파일 러는 입력 크기가 작 으면 모든 것이 잘된다는 것을 알려줍니다. 그러면 입력 크기가 커지고 런타임이 폭발합니다.
사람들은 종종 "이론적"또는 "쓸모없는"또는 "프로파일 링보다 중요하지 않은"것으로 big-O 표기법을 무시합니다. 어느 정도의 큰 복잡성이 의에 대해 이해하지 못한다는 것을 나타냅니다. 그것은 프로파일 러가하는 것과는 다른 문제를 해결합니다. 둘 다 좋은 성능의 소프트웨어 작성에 필수적입니다. 그러나 프로파일 링은 궁극적으로 도구입니다. 문제가 발생하면 이 어디 있는지 알려줍니다..
빅 오 (Big-O) 복잡성은 더 큰 입력에서 코드를 실행하면 코드의 어느 부분이 폭파 될 것인지를 사전에 알려줍니다. 프로파일 러는 그것을 말할 수 없습니다.
예, 서버 측 코드의 경우 문제가 발생하는 하드웨어의 양에 관계없이 병목 현상이 발생하면 배율을 줄일 수 없으므로 확장 할 수 없습니다.
그렇다면 파일 및 네트워크 액세스 차단과 같은 확장 성 문제에 대한 다른 이유가 있습니다. 내부 계산보다 훨씬 느리며 프로파일 링이 BigO보다 더 중요한 이유입니다 .
그게 내가 생각한 것이지만, 인터뷰는 실제로 '여기에 어떤 알고리즘을 사용할 지 말해 주시겠습니까?' 그리고 '그 알고리즘의 복잡성은 무엇입니까'. – beggs
@ Beggs :이 지식은 각 상황에서 적절한 알고리즘을 사용할 수 있어야합니다. 복잡성을 모른 채 어떻게 적절한 것을 고를 수 있습니까? –
@ gs, 나는 동의하지만 인터뷰에서 알고리즘의 Big-O을 인용 할 수 있습니까? 간단한 정렬 및 트리 삽입과 같은 것 이외에도 병합 정렬이 버블 정렬보다 낫다는 것을 알고 있지만 더 복잡한 것에 대해 이야기하기 시작할 때 복잡성을 계산하는 데 시간을 할애 할 필요가 있습니다. – beggs