টাইম এবং স্পেস কমপ্লেক্সিসিটি দিয়ে এলগোরিদম এনালাইসিস
এলগোরিদম এনালাইসিস বলতে একটা এলগরিদমের কার্যকারিতা কেমন সেটা মূল্যায়ন করাকে বুঝায়। বিভিন্ন ইনপুট সাইজের উপর নির্ভর করে একটা এলগোরিদম কেমন আচরণ করবে সেটা যাচাই করা ও মূল্যায়ন করার নামই এলগোরিদম এনালাইসিস। সাধারণত কমপ্লেক্সিসিটির উপর নির্ভর করে কোন একটা এলগোরিদমের কার্যকারিতা ও গ্রহণযোগ্যতা নির্ণয় করা হয়। মূলত দুই ধরণের কমপ্লেক্সিসিটি নিয়ে কাজ করে থাকে একটা হচ্ছে টাইম অন্যটি স্পেস কমপ্লেক্সিসিটি। এই দুটোর মাধ্যমে বুঝা যায় একটা এলগোরিদম সমস্যা সমাধানে কতটা টাইম ও স্পেস নিয়ে কার্যকরী ভূমিকা পালন করতে পারে। মাঝে মাঝে এমন হয় যে স্পেস পর্যাপ্ত থাকলেও সময়টা কম নিতে হয়, সেক্ষেত্রে আমাদের অবশ্যই এমন একটা এলগোরিদম নিতে হবে যেটা কিনা স্পেস অনেক বেশি নিলেও, সমস্যা সমাধানে অনেক কম সময় নেয়। আবার মাঝে মাঝে উলটো বিষয়টিও ঘটতে পারে। তো এখন আমরা এই দুই ধরণের কমপ্লেক্সিসিটি নিয়ে আলোচনা করবো।
কোন একটা নির্দিষ্ট এলগোরিদম তার প্রত্যেকটা ষ্টেপ শেষ করতে ঠিক কতটা সময় নিতে পারে সেটা আমরা টাইম কমপ্লেক্সিসিটির মাধ্যমে বুঝতে পারি।
আবার কোন একটা নির্দিষ্ট এলগোরিদম তার প্রত্যেকটা ষ্টেপ শেষ করতে ঠিক কতটা জায়গা দখল করতে পারে সেক্ষেত্রে আমরা স্পেস কমপ্লেক্সিসিটি ব্যবহার করে বুঝতে পারি।
একটা বিষয় মনে রাখা জরুরি যে একই সাথে কোন একটা এলগোরিদমের স্পেস ও টাইম অপ্টিমাইজ করা সম্ভব না। এই ব্যাপারে space-time trade-off নামের একটা বিখ্যাত প্রিন্সিপ্যাল আছে। এই প্রিন্সিপাল অনুযায়ী টাইম এবং স্পেসের মধ্যে এমন একটা সম্পর্ক থাকে, যেখানে কোন একটা বিষয়কে অপ্টিমাইজ করতে চাইলে অবশ্যই আরেকটা অপ্টিমাইজ করা যায় না। তার মানে যদি আমরা কোন একটা এলগোরিদমের টাইম কমাতে চাই অবশ্যই তার স্পেস বেড়ে যাবে, আবার যদি স্পেস কমাতে চাই, তাহলে টাইম অপ্টিমাইজ করা সম্ভব হবে না।
সাধারণত কমপ্লেক্সিসিটি গুলো কে Big-O দ্বারা প্রকাশ করা হয়। তিন ধরণের কেস নিয়ে মূলত কমপ্লেক্সিসিটি কাজ করে ১. Best Case ২. Average Case ৩. Worst Case. তবে এই কেস গুলোর মধ্য থেকে শুধু মাত্র Worst case নিয়ে কাজ করা হয়। এখন প্রশ্ন আসতে পারে শুধু Worst case নিয়ে কেন কাজ করা হয়? এলগোরিদমের কেজ গুলো সাধারণত নির্ভর করে ইনপুট সাইজ ও ইনপুট ডাটার ধরণের উপর। আর প্রথম দুটো কেজকে সাধারণত ভালো ধরা হয় অন্যদিকে তৃতীয় কেজটার মাধ্যমে একটা এলগোরিদম কতটা খারাপ ভাবে এক্সিকিউট হতে পারে সেটার সম্পর্কে ভালো ধারণা পাওয়া যায়।
এখানে আমি কয়েকটা ব্যাসিক কমপ্লেক্সিটি নিয়ে আলোচনা করবো যেমন O(1), O(n), O(n²), O(log n), O(n log n) এবং O(2^n)। তবে কোন ধরণের ইকুয়েশন নিয়ে আলোচনা করবো না। আমি ধরে নিচ্ছে আপনাদের মিনিমাম ব্যাসিক জানা আছে, কিন্তু কমপ্লেক্সিটি গুলাও ফিল করতে পারছেন না।
O(1):
O(1) টাইম কমপ্লেক্সিসিটি বলতে বুঝায় একটা এলগোরিদম কনস্ট্যান্ট সময়ে কাজটা শেষ করতে পারে। স্পেস কমপ্লেক্সিসিটির ক্ষেত্রেও সেম কনষ্ট্যান্ট স্পেসে কাজটা শেষ করে। একটা উদাহরণ দিলে মন্দ নয়, যখন দুটো ভেরিয়েবলকে যোগ করে আরেকটা ভেরিয়েবলে রাখা হয় যেমন c = a + b, সেক্ষেত্রে টাইম কনষ্টেন্ট কেননা এখানে আমার ইনপুটের উপর সময়ের কোন প্রভাব হচ্ছে না। আবার স্পেসের ক্ষেত্রে ঠিক একইরকম, সব সময় নির্দিষ্ট কয়েকটা ভেরিয়েবল মেমোরির নির্দিষ্ট কিছু জায়গা দখল করছে মাত্র। a, b, c যদি ইন্টেজার হয় এখানে সব সময় 4 বাইট জায়গা নিবে, এর কোন পরিবর্তন আসবে না। কিন্তু এই কাজটা যদি লুপের মধ্যে n সংখ্যকবার করি সেক্ষেত্রে আমার টাইম এবং স্পেস হয়ে যাবে 4n byte অর্থাৎ O(n), যেখানে কনষ্টেন্ট থাকবে না।
O(n):
যখন কোন একটা লুপ n সংখ্যকবার ঘুরে একটা নির্দিষ্ট কাজ সম্পাদন করে সেক্ষেত্রে টাইম কমপ্লেক্সিসিটি হবে O(n) কেননা n এর মান আমাদের কাছে অজানা, বিভিন্ন কিছু হতে পারে। কিন্তু স্পেস কমপ্লেক্সিসিটি হবে O(1)। তবে আমরা যদি লুপে কোন একটা কন্টেইনারে ডাটা রাখতে থাকি সেক্ষেত্রে স্পেস কমপ্লেক্সিসিটি হবে O(n) কেননা তখন প্রোগ্রামটি n সংখ্যক ডাটা ষ্টোর করছে মেমোরিতে।
func SimpleIteration1(arr1 []int) []int {
var arr2 []int
for _, val := range arr1 {
arr2 = append(arr2, val)
}
return arr2
}যেমন SimpleIteration1 এ দেখতে পাচ্ছি একটা ফাঁকা এরে arr2 নেওয়া হয়েছে, আর প্রত্যেক বার ইটারেশনে arr2 তে একটা করে ভেলু যুক্ত হচ্ছে, তাই এই প্রোগ্রামের টাইম এবং স্পেস কমপ্লেক্সিসিটি হবে O(n)।
O(n²):
নিচের উদাহরণের দিকে লক্ষ্য করি,
func SimpleIteration2(n int) [][]int {
var arr2 [][]int
for i := 0; i < n; i++ {
var row []int
for j := 0; j < n; j++ {
row = append(row, j)
}
arr2 = append(arr2, row)
}
return arr2
}SimpleIteration2 তে দেখতে পাচ্ছি একটা দিমাত্রিক (2 dimensional) এরে বা লিষ্ট নেওয়া হয়েছে। তারপর একটা লুপের মধ্যে আরেকট লুপ নেওয়া হয়েছে। যদি বাইরের লুপ একবার ঘুরে, ভিতরের লুপটি n সংখ্যক বার ঘুরবে, অর্থাৎ 1*n, তাহলে আমরা এটাকে এভাবেও লিখতে পারি যে যদি বাইরের লুপ n সংখ্যকবার ঘুরে ভিতরের লুপও n সংখ্যক বার ঘুরবে মানে n*n = n² বা O(n²)। এখানে একটা বিষয় বুঝার আছে সব সময় যে দুটো লুপের মান সমান হবে তা না। যদি এমন হয় বাইরের লুপ ঘুরবে n সংখ্যকবার, ভিতরের লুপ m তাহলে সেক্ষেত্রে টাইম কমপ্লেক্সিসিটি হবে O(n*m)। এখানে স্পেস কমপ্লেক্সিসিটি হবে O(n²) কেননা আমরা একটা দিমাত্রিক ফাঁকা এরে নিয়েছি এবং সেখানে প্রতি ইটারেশনে ভেলু যুক্ত করছি।
O(log n):
কম্পিউটার সাইন্সে মূলত লগারিদমের বেস 2 নিয়ে কাজ করা হয়। যদি আমরা n = 8 ধরি এক্ষেত্রে log(n) এর মান আসে 3। যখন কোন একটা এলগোরিদমের ইনপুট সাইজ প্রত্যেকবার অর্ধেক করে কমতে থাকে সেক্ষেত্রে এটাকে log n দ্বারা প্রকাশ করা হয়। কেন প্রকাশ করা হয়?
এক্ষেত্রে আমরা binary search এলগোরিদমকে উদাহরণ হিসাবে নিতে পারি -
func BinarySearch1(array []int, target int) int {
low, high := 0, len(array)-1
var mid int
for low <= high {
mid = (low + high) / 2
if array[mid] == target {
return mid
}
if array[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}কোডটাকে যদি আমরা একটু লক্ষ্য করি তাহলে দেখতে পাবো mid = (low+high)/2 এর মাধ্যমে ইনপুট সাইজ বার বার অর্ধেক হয়েছে যতক্ষন না পর্যন্ত target ভেলু পায়। তার মানে যদি আমাদের ইনপুট এরে বা লিষ্ট সাইজ 8 হয় সেক্ষেত্রে ক্যালকুলেশন হবে নিম্নরূপ:
8/2 = 4
4/2 = 2
2/2 = 1
এখানে কত গুলো ষ্টেপের মাধ্যমে কাজটি শেষ হয়েছে? উত্তর হবে 3টি। একই ভাবে যদি আমরা ইনপুট সাইজ 256 নিই:
256/2 = 128
128/2 = 64
64/2 = 32
32/2 = 16
16/2 = 8
8/2 = 4
4/2 = 2
2/2 = 1
তাহলে এখানে ষ্টেপ হবে 8 টি।
যদি আমরা log2(256) ক্যালকুলেশন করি উত্তর হবে ষ্টেপের সমান 8।
তার মানে আমাদের কাঙ্ক্ষিত ভেলু পেতে সর্বোচ্চ log n সমতুল্য সময় ব্যয় করতে হবে।
এই ক্যালকুলেশন আমরা আরেকভাবেও করতে পারি। যেকোন ইনপুট সাইজ log10(n) কে log10(2) দ্বারা ভাগ করলে , কাঙ্ক্ষিত ভেলু পাবো। আর এই জন্য binary search এর টাইম কমপ্লেক্সিসিটি O(log n), কিন্তু উপরের কোডের স্পেস কমপ্লেক্সিসিটি O(1)। কেননা এটার রান টাইমে অতিরিক্ত কোন স্পেস দরকার হচ্ছে না প্রোগ্রামের,আমরা শুধু ডিফাইন করা এরেতে বা কন্টেইনারে টারগেট ভেলূ খোঁজার চেষ্টা করেছি মাত্র, কোথাও নতুন কোন ভেলু রাখছি না।
কিন্তু উপরের কোডকে অন্য ভাবেও করতে পারি তা নিম্নরুপ:
func BinarySearch2(array []int, low int, high int, target int, ans []int) []int {
var mid int
for low <= high {
mid = (low + high) / 2
if array[mid] == target {
if !CheckExistence(ans, mid) {
ans = append(ans, mid)
BinarySearch2(array, low, mid-1, target, ans)
BinarySearch2(array, mid+1, high, target, ans)
}
}
if array[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return ans
}এটা একটা ডাইনামিক প্রোগ্রামিং টেকনিক ইউজ করে করা, তবে আমি এখানে ডাইনামিক প্রোগ্রামিং নিয়ে আলোচনা করবো না। টাইম ও স্পেস কমপ্লেক্সিসিটি নিয়ে আলোচনা করবো। এক্ষেত্রে টাইম কমপ্লেক্সিসিটি পূর্বের মতই O(log n) কেননা প্রত্যেকটা ইটারেশনে ইনপুট সাইজ অর্ধেক করে কমে আসছে। কিন্তু এর স্পেস কমপ্লেক্সিসিটি পূর্বের মত নেই, এটার স্পেস কমপ্লিক্সিটি O(log n) হয়ে গেছে, এখানে আমরা দুটো রিকার্সিভ কল দেখতে পাচ্ছি, যারা আমরা রিকার্শন নিয়ে জানি, সেটা হচ্ছে ফাংশন নিজেই নিজেকে কল করে । কাজেই প্রত্যেকটা রিকার্সিভ কলে একটা করে মেমোরি ষ্ট্যাক ক্রিয়েট হয়ে। এক্ষেত্রে মেমোরি ষ্ট্যাক গুলো পূর্বের থেকে অর্ধেক কম হয়ে থাকে, তাই এটার স্পেস কমপ্লেক্সিসিটি O(log n) হবে।
O(n log n):
log n সম্পর্কে ইতোমধ্যে আমরা জেনেছি, কিন্তু n log n কিভাবে হয়ে সেটা এখন ব্যাখ্যা করবো। তো শুরুর আগে একটা উদাহরণ দেখে নেওয়া যাক :
func Merge(a []int, b []int) []int {
var MargeArr []int
lenA, lenB := len(a), len(b)
indexA, indexB := 0, 0
for indexA < lenA && indexB < lenB {
if a[indexA] < b[indexB] {
MargeArr = append(MargeArr, a[indexA])
indexA++
} else {
MargeArr = append(MargeArr, b[indexB])
indexB++
}
}
if indexA < lenA {
MargeArr = append(MargeArr, a[indexA:]...)
} else if indexB < lenB {
MargeArr = append(MargeArr, b[indexB:]...)
}
return MargeArr
}
func MergeSort(arr []int) []int {
var mid int
if len(arr) <= 1 {
return arr
}
mid = len(arr) / 2
left := MergeSort(arr[:mid])
right := MergeSort(arr[mid:])
return Merge(left, right)
}মার্জ শর্টে আমরা দুটো ফাংশন দেখতে পাচ্ছি।
মার্জ শর্ট ফাংশনে দেখতে পাচ্ছি এরেটা বার বার তার আগের ইনপুট সাইজ থেকে অর্ধেক হয়ে যাচ্ছে, তার মানে এটার টাইম এবং স্পেস কমপ্লেক্সিসিটি যথাক্রমে O(log n)।
আবার মার্জ ফাংশনে আমরা দেখতে পাচ্ছি দুটো এরেকে বিভিন্ন টেকনিকের মাধ্যমে একত্র করা হয়েছে এক্ষেত্রে টাইম কমপ্লেক্সিসিটি O(n) আর স্পেস কমপ্লেক্সিসিটি O(n), কেননা এখানে নতুন একটা এরে নেওয়া হয়েছে এবং সেখানে n সংখ্যক সাব এরে গুলো প্রত্যেকটা একে অপরের সাথে তুলনা করা হয়েছে। আর যেহেতু দুটো একত্রে সম্পাদিত হয়েছে তাই আমরা বলতে পারি টাইম এবং স্পেস কমপ্লেক্সিসিটি O(n log n)।
O(2^n):
এটাকে বলা হয় এক্সপনেন্সিয়াল টাইম কমপ্লেক্সিসিটি, যখন প্রত্যেক ইটারেশনে এর ইনপুট ডাটাসেট পূর্বের থেকে দ্বিগুন হয়ে যায়। যদি প্রথম লেভেলে ইনপুট ডাটা সেট একটা হয়, পরের লেভেল সেটা হবে দুটো, এভাবে প্রত্যকটা ডাটা ইনপুটের মান দ্বিগুন হতে থাকে প্রত্যেকটা ইটারেশনে। এটা বুঝার জন্য সবচেয়ে ভালো উদাহরণ হচ্ছে fibonacci সিরিজের সেই বিখ্যাত উদাহরণ।
func fibonacci(n int) int {
if n <= 1 {
return 1
}
return fibonacci(n-1) + fibonacci(n-2)
}আমরা দেখতে পাচ্ছি fibinacci সিরিজটি রিকার্সিভ ওয়েতে সমাধান করা হয়েছে। প্রত্যেক রিকার্সিভ কলে ইনপুট ডাটা দুভাগে ভাগ হয়ে দ্বিগুন আকারে পরবর্তী ষ্ট্যাকে যাচ্ছে — তাই এটার টাইম এবং স্পেস কমপ্লেক্সিসিটি O(2^n)। স্পেস কমপ্লেক্সিসিটি O(2^n) এই জন্য যে প্রত্যেক কলে মধ্যবর্তী রেজাল্ট গুলো ষ্ট্যাকে জমা হয়ে থাকে, আর সেটার জন্য O(2^n) স্পেস দরকার পরে।
এখানে গুটিকয়েক কমপ্লেক্সিসিটি নিয়ে আলোচনা করা হয়েছে, এগুলো ছাড়াও আরো অনেক ধরনের কমপ্লেক্সিসিটি থাকতে পারে। যেমন BFS & DFS এর টাইম এবং স্পেস কমপ্লেক্সিসিটি হচ্ছে O(E+V)। কাজেই নিজে নিজে কিছু প্র্যাকটিস করতে হবে। তবে ব্যাসিক এল্গোরিদম এনালাইসিস করার ক্ষেত্রে এগুলো যথেষ্ট। একটা বিষয় মনে রাখা দরকার যখন আমরা কোন এলগরিদম ডিজাইন করবো, সেটার কমপ্লেক্সিসিটি পুরোপুরি নির্ভর করবে আমাদের রিকুয়ারিমেন্ট এর উপর। আরেকটা বিষয় হচ্ছে ম্যাক্সিমাম ক্ষেত্রে দেখা যায় স্পেস কমপ্লেক্সিসিটিকে টাইম কমপ্লেক্সিসিটি থেকে কম গুরুত্ব দেওয়া হয়, এটার কারণ হচ্ছে বর্তমানে ষ্টোরেজের অভাব নেই, কিন্তু ইউজার এক্সপেরিয়েন্স দ্রুত হওয়া চায়। আমাদের কাছে মনে হতে পারে একই ধরণের কাজ করা এলগোরিদম গুলোতে এটা বেষ্ট, কিন্তু বাস্তবের ক্ষেত্রে রিকুয়ারিমেন্ট অন্য ধরণের হলে, অবশ্যই আমাদের যেটা মনে হচ্ছে বেষ্ট সেটা বাদ দিতে হতে পারে, পরিস্থিতির উপর নির্ভর করে এল্গোরিদম এনালাইসিস করায় হচ্ছে গুড প্র্যাকটিস।
written by Nur Amin Sifat
