Big-Ω 하한과 witness

오늘의 질문

충분히 큰 n에서 f(n) ≥ c·g(n)을 강제하는 입력 또는 계산 구조를 제시한다. 이를 생략하면 상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다.에서도 그럴듯한 Big-O나 벤치마크 숫자는 만들 수 있지만 실행 가능한 선택과 반증 가능한 근거를 남길 수 없습니다.

아직 답을 몰라도 괜찮아요. 아래 작은 예시를 보고 먼저 예상해 보세요.

01 · 같이 연습해요

작은 문제부터 하나씩 직접 풀어봐요

먼저 예상하고, 한 단계씩 확인하고, 막힌 곳을 고쳐 봐요. 도움을 열어도 괜찮아요. 도움을 본 문제는 나중에 모양을 바꿔 다시 풀어보면 됩니다.

연습에서 작성 중인 답0 / 8

01
찾아보기 · 기초
cx21 recognize · Big-Ω 하한과 witness: Big-Omega·lower bound 표식 중 “충분히 큰 n에서 f(n) ≥ c·g(n)을 강제하는 입력 또는 계산 구조를 제시한다.”을 만족하는 판정을 고른다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
정답과 비교
02
먼저 생각하기 · 기초
cx21 predict · Big-Ω 하한과 witness: “상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다.” 조건에서 비용·메모리·판정이 어떻게 바뀔지 실행 전에 봉인한다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
움직임과 비교
03
순서 따라가기 · 익힌 것을 써보기
cx21 trace · Big-Ω 하한과 witness: Big-Omega → lower bound → forcing witness 순서로 입력 계약에서 lower-bound inequality와 forcing input family까지 최초 비용 모델 이탈을 추적한다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
움직임과 비교
04
내 말로 설명하기 · 익힌 것을 써보기
cx21 explain · Big-Ω 하한과 witness: 충분히 큰 n에서 f(n) ≥ c·g(n)을 강제하는 입력 또는 계산 구조를 제시한다.이 필요한 이유와 lower-bound inequality와 forcing input family만으로 입증할 수 없는 범위를 설명한다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
설명 기준과 비교
05
빈칸 채우기 · 익힌 것을 써보기
cx21 complete · Big-Ω 하한과 witness: 누락된 입력 차원·비용 단위·경계 또는 판정 칸을 채워 “반드시 수행되는 연산을 찾아 Ω 경계를 증명한다.”을 완성한다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
답과 설명 함께 비교
06
틀린 곳 고치기 · 익힌 것을 써보기
cx21 debug · Big-Ω 하한과 witness: AI가 만든 분석에 “상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다.” 반례를 주입하고 최초 잘못된 가정만 수정한다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
답과 설명 함께 비교
07
직접 만들기 · 새 문제
cx21 implement · Big-Ω 하한과 witness: 반드시 수행되는 연산을 찾아 Ω 경계를 증명한다.을 frozen synthetic input family에 적용해 lower-bound inequality와 forcing input family를 생성한다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
정답과 비교
08
새 문제에 써보기 · 새 문제
cx21 transfer · Big-Ω 하한과 witness: 입력 읽기·comparison lower bound로 판단을 옮겨 보존할 invariant와 달라지는 비용 모델을 방어한다.
이 문제는 주어진 내용과 정답 기준을 더 만드는 중이에요. 지금 적은 답은 연습 메모로만 저장돼요.
관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.
정답 대신 4단계 힌트 보기
1. 관찰
  상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.
2. 개념
  Big-Omega·lower bound·forcing witness를 정의·가정·관찰로 나눠 적으세요.
3. 다음 도움
  내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.
설명 기준과 비교

8개 답이 남았습니다.

02 · 막힌 곳을 찾아요

틀린 답에서 생각이 갈라진 첫 지점 찾기

헷갈림 01

상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다.

겉으로 보이는 막힘: Big-Ω 하한과 witness 식은 계산되지만 어떤 입력 family와 workload에 대한 값인지 재현할 수 없다.
막힌 까닭: 충분히 큰 n에서 f(n) ≥ c·g(n)을 강제하는 입력 또는 계산 구조를 제시한다.을 분석 전에 봉인하지 않았다.
다시 해보는 방법: 반드시 수행되는 연산을 찾아 Ω 경계를 증명한다.에서 입력 차원·범위·분포·반복 횟수와 비용 단위를 먼저 고정하고 lower-bound inequality와 forcing input family를 다시 만든다.

헷갈림 02

AI가 Big-Ω 하한과 witness 구현과 expected complexity를 같은 답변에서 생성한다.

겉으로 보이는 막힘: 코드와 oracle이 같은 누락 가정을 공유해 상한만 증명하고 알고리즘이 그보다 실제로 더 작을 가능성을 배제하지 못한다.가 false green으로 남는다.
막힌 까닭: AI-off baseline과 독립 exact-count 또는 adversarial family를 먼저 만들지 않았다.
다시 해보는 방법: 기존 contract를 보존한 채 AI diff만 검토하고 별도 작성한 forcing witness 반례로 재검증한다.

헷갈림 03

lower-bound inequality와 forcing input family의 한 측정값이나 차트만 최종 결론으로 제출한다.

겉으로 보이는 막힘: 환경·warm-up·noise·constant·input distribution이 바뀌면 결론을 재현하거나 반박할 수 없다.
막힌 까닭: 이론적 경계·실험 protocol·raw observation·human verdict를 분리하지 않았다.
다시 해보는 방법: lower-bound inequality와 forcing input family에 환경 manifest·입력 seed·반복값·예측·반례·잔여 한계를 추가하고 사람이 승인 범위를 서명한다.

03 · 내게 맞는 도움 고르기

같은 목표를 원하는 도움만큼 연습해요

안내 받으며

안내형

Big-Omega · lower bound · forcing witness 카드와 4단계 표를 제공하고 숫자·기호·색상 외에도 case·assumption·budget label을 함께 표시한다.

Big-Ω 하한과 witness에서 입력 family와 primitive operation을 고정하고 비용 경계와 측정값을 대조해 판정을 내리는 설명도에서 색상뿐 아니라 입력 family·비용 단위·case·bound·budget·verdict를 문자와 선 종류로 함께 표시한다.

혼자 해보기

내 힘으로

Big-Ω 하한과 witness의 미공개 입력 family에서 semantics·cost model·bound·budget verdict를 독립적으로 재구성하는 능력의 처음 보는 frozen synthetic 입력 family를 AI 없이 먼저 분석하고 exact count·bound·budget 판정을 봉인한 뒤 실행 관찰과 대조한다.

공식 정의·문법·도구 사용법은 열 수 있지만 해당 변형의 exact count, tight bound, 반례, hidden fixture와 최종 verdict는 먼저 제공하지 않는다.

더 도전하기

심화형

입력 읽기·comparison lower bound에서 입력 차원을 둘 이상으로 일반화하고 adversarial family와 lower-bound witness를 추가해 선택을 다시 방어한다.

더 촘촘한 모델은 설명력과 반례 탐지력을 높이지만 측정·문서 비용도 늘리므로 decision-changing assumption을 우선 기록한다.