나는 시간과 기억의 복잡성의 개념이 compsci 과정을 졸업하는 사람들에게 필수라는 인상을 받았다. 그러나 공학을 공부 한 후에는 그것이 사실인지 전혀 모른다. 최근에 그 개념을 모르는 지역 대학 졸업생들을 인터뷰 한 것에 놀랐습니다. 내 질문은 다음과 같습니다.
계산 복잡성의 개념이 소프트웨어 개발자에게 중요합니까? 그리고 학부 과정에서 가르쳐야합니까?
답변
대부분의 대학에서 시간과 기억의 복잡성이 과정의 일부라고 생각합니다.
이제 이러한 “복잡성”은 매우 탄력적 인 주제입니다. 사람들이 “ZPP는 다항식 시간에 확률 론적 튜링 머신에서 제로 오류로 해결할 수있는 복잡한 결정 문제의 결정 문제”와 같은 모든 이론을 실제로 알아야하는지 여부입니다. 그런 종류의 물건은 의문의 여지가 있습니다. 저는 개인적으로 소프트웨어 개발과 무관 한 이러한 고급 이론을 고려합니다.
반대로, 모든 개발자는 사용하는 데이터 구조와 알고리즘의 시간 / 공간 복잡성을 알고 있어야합니다.
답변
많은 초보자들은 미세 최적화 강박 관념에 시달립니다. 학습 comp. 복잡성으로 인해 학생들은 내 경험에서 성능과 확장 성을 추정하는 훨씬 실용적인 방법으로 학생들을 인도합니다.
답변
내가 본 것으로부터, 공식적인 컴퓨터 과학 교육에서 big-O 표기법과 시간 및 기억의 복잡성이 많이 강조되는 것 같습니다. 말하고 쓰십시오.
비록 일반적인 아이디어와 개념이 중요하다고 생각하지만, 의사 소통의 목적을 제외하고는 그것의 공식화 (big-O 표기법 및 다양한 용어와 같은)가 거의 중요하지 않다고 생각합니다. 누군가가 공식적인 표기법과 용어에 익숙하지 않다고해서 특정 경우에 한 알고리즘이 다른 알고리즘보다 어떻게, 왜 빠를 지 알 수 없다는 의미는 아닙니다. 균형 이진 트리를 검색하는 데 걸리는 시간은 트리의 작동 방식을 이해하고 합리적으로 높은 수준을 이해한다면 공식적인 의미에서 복잡성 이론에 대해 먼저 배우지 않고 노드 수의 기본 2 로그와 관련이 있음을 알 수 있습니다. 학교 수학. 복잡성과 메모리 사용에주의를 기울여야 할 때를 알고, 일반적이고 최악의 경우를 고려하는 것이 중요하지만 어떤 사람들은 그렇지 않습니다.
표기법과 용어는 의사 소통에 중요해집니다. 그들은 알고리즘 성능의 정량화를 다른 사람에게 전달하는 좋은 방법을 제공합니다. 논문과 설명에 자주 나오므로 이해하기 쉽도록 최소한 모호하게 이해하는 것이 좋습니다.
예, 개념 이 중요합니다 (자원과 시간이 충분하지만 데이터가 충분하지 않은 경우에는 덜 중요합니다). 그러나 개념은 중요하지만 개념화는 그다지 중요하지 않으며 표기법과 용어가 개념 자체와 동일하지 않다는 점을 기억해야합니다.
편집하다:
공식적으로 공부 한 사람만큼 개념을 이해한다고 주장하지는 않지만 많은 일반적인 아이디어가 의미가 있습니다. 나는 이것을 공식적으로 연구하는 데 가치가 있다고 생각하지만 그 가치 중 일부는 여전히없이 존재할 수 있습니다.
개념을 소개하는 것 (공식 연구 외부)은 사람들이 데이터 구조에 얼마나 많은 메모리 오버 헤드가 있는지, 알고리즘에 어떤 단계가 있으며, 이러한 데이터가 다른 데이터로 어떻게 바뀌는 지에 대해 생각하도록 장려하는 것이 좋다고 생각합니다.
또한 트리가 균형을 잡을 때 발생하는 일과 가능한 한 불균형 할 때 발생하는 일을 고려하거나 대부분의 노드에있는 트리의 레벨 수 또는 더 많은 노드 수를 고려하는 것과 같은 가상의 상황 및 변경 사항을 고려하는 데 도움이됩니다. 깊이가 한 수준 증가하면 길게 누릅니다. 이러한 사고 방식은 일반적으로 복잡성을 볼 때뿐만 아니라 프로그래머에게도 유용합니다. 알고리즘과 데이터 구조가 서로 다른 상황에서 어떻게 수행되는지에 대한 생각에 적용된다면 복잡성에 대한 공식적인 검토와 같은 방향을 자연스럽게 가리킨다.
답변
예
복잡성의 기본을 이해하는 것이 중요하며 학부생으로서 배우는 것이어야합니다. 사실 나는 데이터 구조에 대해 어떤 클래스에서 가르치는가에 대해 일반적으로 다룰 것이라고 생각합니다. 나는 이해하지 못하거나 기억하지 못하는 졸업생을 이해할 수 있지만, 복잡성의 기초를 배우지 않은 것을 볼 수는 없습니다.
업데이트 : 중요한 이유
특정 작업에서 데이터베이스 마이그레이션을하고있었습니다. 마이그레이션이 완료되어야하는 마감 시간이있었습니다. 대본을 쓴 사람은 복잡하지 않았습니다. 불행히도, 아무도 자신이 스크립트에서 사용한 논리를 자세히 보지 않았습니다. 그는 해시 테이블 대신 이중 중첩 루프를 사용하는 것 이외의 세부 사항을 기억하지 못합니다. 일주일 동안 스크립트를 실행 한 후 논리를 살펴보고 문제를 깨달았습니다. 변경 후 완료하는 데 5 시간 정도 걸렸습니다. 복잡성을 이해하지 못하는 사람으로 인해 마이그레이션 완료 기한을 거의 놓쳤습니다.
요점은 실수로 큰 속도로 느린 것을 만들거나 작업이 완료되기 전에 항상 메모리가 부족한 것을 만드는 것이 쉽다는 것입니다. 더 많은 메모리를 가진 빠른 컴퓨터는 작은 실수를 완화 할 수 있지만 복잡한 문제는 완화 할 수없는 경우가 많습니다.
답변
“중요한지”묻는 것이 다소 모호하다는 것을 알았습니다.
이 세상에서 가장 작은 지식이 그들의 의견에 어떻게 엄격하게 요구되는지에 대해 많은 사람들이 복음을 전합니다. 그러나 그것은 모든 것을 알 수 없기 때문에 무의미합니다. 직무가 요구하는 요구 사항을 충족시키는 데 도움이되지 않으면 기 대해서는 안됩니다. 나는 취미 나 자의적인 개인 취향의 문제가 아니라면 일반적으로 교육 전제 조건에 더 실용적인 접근 방식을 선호합니다.
매우 효율적인 코드 또는 혁신적인 인프라 알고리즘을 작성할 것으로 예상되는 프로그래머에게 중요합니까? 예.
기존의 웹 애플리케이션을 개발하는 프로그래머에게 중요합니까? 오픈 소스 환경에서 관리하지 않고도 효율적으로 구현할 수 있습니다.
응용 프로그램 용 GUI를 개발하는 프로그래머에게 중요합니까? 성공적인 GUI 프레임 워크는 모든 작은 세부 사항을 추상화하기 때문에 아마도 아닙니다.
다른 어떤 것과 마찬가지로 항상 아는 것이 좋지만, 많은 (또는 대부분의) 프로그래머가 단순히 직업을 수행하는 것을 고용주가 만족시키기까지하는 것은 아닙니다.
다른 한편으로, 기초 및 이론 교육을 찾기 위해 고등 연구에 등록한 경우, 정의보다 실질적으로 이론적 인 주제를 학습해야합니다. 제 생각에는 CompSci가 필수적입니다. 학생들은 미적분학에 대해 배우는 것이 중요한 것처럼 복잡성에 대해 배웁니다.
어쨌든 CompSci는 언제부터합니까. 프로그램은 사람들에게 좋은 프로그래머가되는 방법을 가르쳐? 이를 위해 전문 교육 프로그램과 실무 경험을 보유하고 있습니다 (나와 공유 할 수있는 동료 프로그래머).