টাইম কমপ্লেক্সিটি কম্পিউটার সায়েন্স থেকে আপনি শিখতে পারেন সবচেয়ে আকর্ষণীয় কনসেপ্টগুলির একটি, এবং এটি বুঝতে আপনাকে কোনো ডিগ্রির দরকার নেই!
এটি আকর্ষণীয় কারণ এটি আপনাকে দেখতে সাহায্য করে কেন একটি নির্দিষ্ট অ্যালগরিদম বা প্রোগ্রাম ধীর হতে পারে এবং আপনি কী করতে পারেন তা দ্রুত করতে।
আপনি এটি আপনার নিজের কোডে প্রয়োগ করতে পারেন।
এটি কম্পিউটার সায়েন্স বইয়ে পাওয়া সব ফ্যান্সি অ্যালগরিদমের বাইরে চলে যায়, যেমন আমি পরবর্তীতে আপনাকে প্রদর্শন করব।
কিন্তু প্রথমে আমাদের কী ধীর এবং কী দ্রুত সেটি নিয়ে কথা বলতে হবে।
ধীর বনাম দ্রুত
১ মিলিয়ন সংখ্যা সর্ট করতে ১৫০ms (মিলিসেকেন্ড) লাগলে সেটি ধীর নাকি দ্রুত?
আমি মনে করি এটি খুব দ্রুত, কিন্তু এটি সেই প্রশ্ন নয় যা টাইম কমপ্লেক্সিটি উত্তর দিতে চায়।
আমরা জানতে চাই কীভাবে একটি অ্যালগরিদম পারফর্ম করবে যখন "ইনপুট সাইজ" বড়বে।
যখন আমরা "ইনপুট সাইজ" বলি তখন আমরা ফাংশন বা মেথডের আর্গুমেন্টের কথা বলি। যদি একটি মেথড একটি স্ট্রিং আর্গুমেন্ট হিসেবে নেয় তবে সেটিই ইনপুট, এবং স্ট্রিং-এর দৈর্ঘ্য হলো ইনপুট সাইজ।
Big O নোটেশন
Big O নোটেশন দিয়ে আমরা অ্যালগরিদমগুলো তাদের পারফরম্যান্স অনুযায়ী ক্লাসিফাই করতে পারি।
এটি এরকম দেখায়:
O(1)
এই কেসে O(1) প্রতিনিধিত্ব করে একটি "কনস্ট্যান্ট টাইম" অ্যালগরিদম।
এর মানে অ্যালগরিদমটি সবসময় একই সময় নেবে তার কাজ শেষ করতে, আপনাকে কতটুকু কাজ করতে হোক না কেন।
আরেকটি হলো "লিনিয়ার টাইম":
O(n)
যেখানে "n" প্রতিনিধিত্ব করে ইনপুটের সাইজ (স্ট্রিং সাইজ, অ্যারে সাইজ, ইত্যাদি)। এর মানে অ্যালগরিদমটি ১:১ সম্পর্কে ইনপুট সাইজ অনুযায়ী কাজ শেষ করবে, তাই ইনপুট সাইজ ডাবল করলে কাজ শেষ করতে লাগने वाला সময়ও ডাবল হয়ে যাবে।
এখানে একটি টেবিল:
| নোটেশন | নাম | বিবরণ |
|---|---|---|
| O(1) | কনস্ট্যান্ট | সবসময় একই সময় নেয়। |
| O(log n) | লগারিদমিক | প্রতি লুপ ইটারেশনে কাজের পরিমাণ ২ দিয়ে ভাগ হয় (বাইনারি সার্চ)। |
| O(n) | লিনিয়ার | কাজ শেষ করতে লাগने वाला সময় ইনপুট সাইজের সাথে ১ থেকে ১ সম্পর্কে বড়ে। |
| O(n log n) | লিনিয়ারিথমিক | এটি একটি নেস্টেড লুপ, যেখানে ইনার লুপ log n টাইমে চলে। উদাহরণ inclou quicksort, mergesort এবং heapsort। |
| O(n^2) | কোয়াড্রাটিক | কাজ শেষ করতে লাগنے वाला সময় input size ^ 2 সম্পর্কে বড়ে। আপনি এটিকে চিনতে পারেন যখন আপনার একটি লুপ থাকে যা সব এলিমেন্টের ওপর ঘুরে এবং লুপের প্রতিটি ইটারেশনও সব এলিমেন্টের ওপর ঘুরে। আপনার একটি নেস্টেড লুপ আছে। |
| O(n^3) | কিউবিক | n^2-এর মতোই, কিন্তু সময় n^3 সম্পর্কে ইনপুট সাইজের সাথে বড়ে। ট্রিপল নেস্টেড লুপ খুঁজে বের করুন এটিকে চেনার জন্য। |
| O(2^n) | এক্সপোনেনশিয়াল | কাজ শেষ করতে লাগنے वाला সময় 2 ^ input size সম্পর্কে বড়ে। এটি n^2-এর চেয়ে অনেক ধীর, তাই সেগুলো গুলিয়ে ফেলবেন না! একটি উদাহরণ হলো রিকার্সিভ ফিবোনাচি অ্যালগরিদম। |
অ্যালগরিদম অ্যানালাইসিস
আপনি আপনার ইন্টুইশন ডেভেলপ করতে পারেন যদি ইনপুটকে "n" এলিমেন্টের একটি অ্যারে হিসেবে চিন্তা করেন।
কল্পনা করুন আপনি সব এলিমেন্ট খুঁজতে চান যা ইভেন নাম্বার, এটি করার একমাত্র উপায় হলো প্রতিটি এলিমেন্ট একবার পড়ে শর্তটি মেলে কিনা দেখা।
[1,2,3,4,5,6,7,8,9,10].select(&:even?)
আপনি নাম্বারগুলো স্কিপ করতে পারবেন না কারণ আপনি যে নাম্বারগুলো খুঁজছেন সেগুলো মিস করতে পারেন, তাই এটি একটি লিনিয়ার টাইম অ্যালগরিদম O(n)।
একই সমস্যার ৩টি ভিন্ন সমাধান
সিঙ্গেল উদাহরণ অ্যানালাইসিস আকর্ষণীয়, কিন্তু যা আসলে এই আইডিয়াটি বুঝতে সাহায্য করে সেটি হলো একই সমস্যা কীভাবে ভিন্ন সমাধান দিয়ে সমাধান করা যায়।
আমরা একটি স্ক্র্যাবল সমাধান চেকারের জন্য ৩টি কোড উদাহরণ এক্সপ্লোর করব।
স্ক্র্যাবল হলো একটি গেম যা ক্যারেক্টারের একটি লিস্ট দিয়ে (যেমন ollhe) আপনাকে শব্দ তৈরি করতে বলে (যেমন hello) এই ক্যারেক্টারগুলো ব্যবহার করে।
প্রথম সমাধান:
def scramble(characters, word)
word.each_char.all? { |c| characters.count(c) >= word.count(c) }
end
আপনি জানেন এই কোডের টাইম কমপ্লেক্সিটি কী? চাবিটি count মেথডে আছে, তাই নিশ্চিত হন আপনি বুঝতে পারেন সেই মেথডটি কী করে।
উত্তর: O(n^2)।
কারণ হলো each_char দিয়ে আমরা স্ট্রিং word-এর সব ক্যারেক্টারের ওপর ঘুরছি। সেটি একলা একটি লিনিয়ার টাইম অ্যালগরিদম O(n) হত, কিন্তু ব্লকের ভেতরে আমাদের count মেথড আছে।
এই মেথডটি কার্যকরভাবে আরেকটি লুপ যা আবার স্ট্রিং-এর সব ক্যারেক্টারের ওপর ঘুরে সেগুলো কাউন্ট করতে।
দ্বিতীয় সমাধান
ঠিক আছে।
আমরা কীভাবে ভালো করতে পারি? কি কোনো উপায় আছে কিছু লুপ বাঁচাতে?
ক্যারেক্টার কাউন্ট করার বদলে আমরা সেগুলো রিমুভ করতে পারি, যাতে আমাদের কম ক্যারেক্টারের ওপর ঘুরতে হয়।
দ্বিতীয় সমাধান:
def scramble(characters, word)
characters = characters.dup
word.each_char.all? { |c| characters.sub!(c, "") }
end
এটি একটু বেশি আকর্ষণীয়। সেরা কেসে এটি count ভার্সন চেয়ে অনেক দ্রুত হবে, যেখানে আমরা যে ক্যারেক্টারগুলো খুঁজছি সেগুলো স্ট্রিং-এর শুরুতে আছে।
কিন্তু যখন ক্যারেক্টারগুলো সব শেষে থাকে, word-এ কীভাবে আছে সেটির বিপরীত ক্রমে, পারফরম্যান্স count ভার্সনের মতোই হবে, তাই আমরা বলতে পারি এটি এখনও একটি O(n^2) অ্যালগরিদম।
আমাদের কেস যেখানে word-এর কোনো ক্যারেক্টার characters-এ নেই সেটি নিয়ে চিন্তা করতে হয় না, কারণ all? মেথডটি থামবে যতক্ষণ না sub! false ফেরত দেয়। কিন্তু আপনি এটা শুধু জানতে পারবেন যদি আপনি রুবি ব্যাপকভাবে অধ্যয়ন করেন, রেগুলার রুবি কোর্সের চেয়ে অনেক বেশি।
আরেকটি আপপ্রোচ ট্রাই করি
যদি আমরা ব্লকের ভেতরে যেকোনো ধরনের লুপ সরিয়ে ফেলি? আমরা একটি হ্যাশ দিয়ে এটি করতে পারি।
def scramble(characters, word)
available = Hash.new(1)
characters.each_char { |c| available[c] += 1 }
word.each_char.all? { |c| available[c] -= 1; available[c] > 0 }
end
হ্যাশ ভ্যালু পড়া এবং লেখা একটি O(1) অপারেশন, যা মানে এটি খুব দ্রুত, özellikle লুপের তুলনায়।
আমাদের এখনও দুটি লুপ আছে:
হ্যাশ টেবিল বানানোর জন্য একটি, এবং চেক করার জন্য একটি। যেহেতু এই লুপগুলো নেস্টেড নয়, এটি একটি O(n) অ্যালগরিদম।
যদি আমরা এই ৩টি সমাধান বেঞ্চমার্ক করি তবে আমরা দেখতে পাব আমাদের অ্যানালাইসিস ফলাফলের সাথে মেলে:
hash 1.216667 0.000000 1.216667 ( 1.216007) sub 6.240000 1.023333 7.263333 ( 7.268173) count 222.866644 0.073333 222.939977 (223.440862)
এখানে একটি লাইন চার্ট:
কিছু বিষয় লক্ষ্য করুন:
- Y অক্ষ (ভার্টিক্যাল) কত সেকেন্ড লাগলো কাজ শেষ করতে সেটি রিপ্রেজেন্ট করে, X অক্ষ (হরিজন্টাল) ইনপুট সাইজ রিপ্রেজেন্ট করে।
- এটি একটি লগারিদমিক চার্ট, যা একটি নির্দিষ্ট রেঞ্জে ভ্যালু কম্প্রেস করে, কিন্তু বাস্তবে
countলাইনটি অনেক বেশি ঢালু। - আমি এটিকে লগারিদমিক চার্ট বানালাম যাতে আপনি একটি আকর্ষণীয় ইফেক্ট পরিচিত হতে পারেন, খুব ছোট ইনপুট সাইজে
countআসলে দ্রুত!
সারসংক্ষেপ
আপনি অ্যালগরিদমিক টাইম কমপ্লেক্সিটি, Big O নোটেশন এবং টাইম কমপ্লেক্সিটি অ্যানালাইসিস সম্পর্কে শিখতে পেরেছেন। আপনি একই সমস্যার ভিন্ন সমাধান তুলনা এবং তাদের পারফরম্যান্স অ্যানালাইসিস করার কিছু উদাহরণও দেখতে পেরেছেন।
আশা করি আপনি কিছু নতুন এবং আকর্ষণীয় শিখতে পেরেছেন!
যদি শিখতে পেরেছেন তবে এই পোস্টটি সোশ্যাল মিডিয়ায় শেয়ার করুন এবং নিউজলেটার সাবস্ক্রাইব করুন যদি এখনো না করে থাকেন যাতে আমি আপনাকে এরকম আরও কন্টেন্ট পাঠাতে পারি।
পড়ার জন্য ধন্যবাদ।
