Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:تئوری مقدماتی سوم:سوال ۲

سوال ۲

درختی داریم که ‎n‎ راس دارد. در هر مرحله می‌توانیم به ازای هر مولفه از این درخت دقیقا یکی از ‎۲‎ کار زیر را انجام دهیم.

  • ‎ یک یال دلخواه را از مولفه حذف کنیم.
  • ‎ همه‌ی برگ‌‌ها را در مولفه حذف کنیم.

دقت کنید که در یک مرحله می‌توان روی دو مولفه کار متفاوتی انجام داد. ثابت کنید:

  1. به ازای هر درخت می توان مراحل را طوری انجام داد که در ‎O(n)‎ مرحله همه ی یال‌ها حذف بشوند.
  2. به ازای هر ‎n‎ مثالی بزنید که به ‎Ω(n)‎ مرحله نیاز باشد تا همه‌ی یال‌ها حذف شوند.

ابزار صفحه