‏پیچیدگی O(n²) که سرورت رو از پا درمیاره

یه تیم یه فیچر روز سه‌شنبه دیپلوی کرد. تا روز پنج‌شنبه، لیتنسی p99 از ۸۰ میلی‌ثانیه به ۱۴ ثانیه رسیده بود. هیچ‌چیزی عوض نشده بود جز تعداد کاربرا. مقصر؟ سه خط کد که موقع ریویو کاملاً معقول به نظر می‌رسیدن ولی پیچیدگی O(n²) داشتن — یعنی با دو برابر شدن داده، کار چهار برابر می‌شه.

پیچیدگی O(n²) چرا اینقدر خطرناکه؟ چون در محیط توسعه با ۱۰ تا رکورد هیچ مشکلی نشون نمی‌ده، ولی در پروداکشن با ۲۰,۰۰۰ کاربر به ۴۰۰ میلیون مقایسه می‌رسه. الگوی اصلیش هم همیشه یه چیزه: یه عملیات جستجو داخل یه حلقه. متدهایی مثل .find()، .includes() و .indexOf() همشون O(n) هستن — وقتی داخل یه map یا filter بذاریشون، نتیجه O(n²) می‌شه.

یکی از رایج‌ترین الگوها اینه که با یه Set می‌شه فوری درستش کرد:

// قبل: O(n * m)
const activeUsers = allUsers.filter(u => activeIds.includes(u.id));

// بعد: O(n + m)
const activeSet = new Set(activeIds);
const activeUsers = allUsers.filter(u => activeSet.has(u.id));

Set.has() برخلاف Array.includes()، پیچیدگی O(1) داره و این یه تفاوت اساسیه.

یه الگوی رایج دیگه مشکل N+1 توی کوئری‌های دیتابیسه. وقتی اول همه سفارش‌ها رو می‌گیری، بعد برای هر سفارش یه کوئری جدا می‌زنی که آیتم‌هاش رو بیاره، با ۱۰۰۰ سفارش به ۱۰۰۱ رفت‌وبرگشت به دیتابیس می‌رسی. راه‌حل یه JOIN یا یه batch query با IN هست که همه داده‌ها رو یه‌جا می‌آره.

همچنین صاف کردن درخت‌های تودرتو با spread operator داخل reduce هم O(n²) میشه چون هر بار آرایه جدید می‌سازه. پاس دادن یه آرایه مشترک به عنوان accumulator این مشکل رو حل می‌کنه.

برای اینکه این مشکلات رو قبل از پروداکشن بگیری، چند کار می‌شه کرد: با داده‌های واقعی پروفایل بگیر — تست با ۱۰ رکورد در مقابل پروداکشن با ۱۰۰,۰۰۰ رکورد عملاً چیزی رو اندازه نمی‌گیره. توی کد ریویو دنبال .find()، .includes() و .indexOf() داخل .map() یا .filter() بگرد. برای لیتنسی هشدار بذار — O(n²) معمولاً تدریجی خراب می‌شه نه یهویی، پس ترند رو باید دنبال کرد.

نکات کلیدی:

• Array.includes() و Array.find() هر دو O(n) هستن و داخل حلقه به O(n²) می‌رسن
• Set.has() و Map.get() هر دو O(1) هستن — اول از اون‌ها استفاده کن
• مشکل N+1 توی دیتابیس همون الگوی O(n²) روی شبکه‌ست
• spread operator داخل reduce بازگشتی می‌تونه O(n²) بسازه
• تست با داده‌های کوچیک این مشکلات رو پنهان می‌کنه؛ با داده واقعی پروفایل بگیر