মডিউল ২_৪ঃ কমপ্লেক্সিটি অ্যানালাইসিস

এখন আমরা bfs এলগোরিদম এর কমপ্লেক্সিটি এনালাইসিস করার চেষ্টা করব।

উপরের গ্রাফটির দিকে খেয়াল করি। এখানে ৪টি নোড আছে ও ৬ টি এজ আছে।আমরা যদি একটু মনে করে দেখি আমাদের ইম্পিমেন্টেশনটা তাহলে দেখব যে আমরা প্রতিটি নোড এ একবার গিয়েছি ও প্রতিটি এজ এও একবার এই গিয়েছি।যদি সোর্স ০ থেকে ধরি তাহলে ০ থেকেই আমরা ১,২ ও ৩ এ ভিজিট করতে পারব। এই ক্ষেত্রে ভিজিটেড এ্যারেতে ১,২,৩ true হইয়ে যাবে তাই পরবর্তী কোনো নোড থেকে এইসব নোড এ আর যাওয়া হবে না।তাই bfs এর টাইম কমপ্লেক্সিটি হবে O(V+E)|এখানে v দ্বারা vertex/node এবং E দ্বারা edge সংখ্যা বোঝানো হয়েছে।

এবার আসি স্পেস কমপ্লেক্সিটি এর বিষয়ে। এখানে আমরা অ্যাডজেসেন্সি লিস্ট বানানোর জন্য একটা vector ব্যবহার করেছি ,একটা ভিজিটেড অ্যারে ব্যবহার করেছি বুলিয়ান টাইপের আর একটা কিউ ব্যবহার করেছি। তাই এদের স্পেস কমপ্লেক্সিটি হওয়া উচিত O(V)|

তবে worst case এ এটা O(N^2) হতে পারে।

কিভাবে সেটা একটু ব্যাখা করার চেষ্টা করি।

উপরের গ্রাফটিতে প্রত্যেকটি নোড একে অপরের সাথে কানেক্টেড। এদের অ্যাডজেসেন্সি লিস্ট যদি বানানো হয় তাহলে

০->১,২,৩,৪

১->০,২,৩,৪

২->০,১,৩,৪

৩->০,১,২,৪

৪->০,১,২,৩

তাহলে এখানে দেখো যে প্রতি n সংখ্যক নোডের জন্য n-1 সাইজের লিস্ট বিদ্যমান। তাই এই ক্ষেত্রে স্পেস কমপ্লেক্সিটি হবে O(N^2)|