আমরা একটু খেয়াল করলেই দেখি
আজকাল অনেক সুন্দর সুন্দর সফটওয়্যার তৈরি হচ্ছে।ইন্ডাস্ট্রি লেভেলে অনেক সময়ই
অ্যালগোরিদমের জটিলতার দিকে নজর দেয়া হয়না।এটা অনেকটা তত্ত্বীয় কম্পিউটার
বিজ্ঞানের বিষয়।আমরা জানি অ্যালগোরিদমের জটিলতাকে বিগ ও (bog O) দিয়ে প্রকাশ করা হয়।এটা
দিয়ে বোঝা যায় অ্যালগোরিদমটা কতটা দ্রুত কাজ করে।যেহেতু এটা অ্যালগোরিদমের
দ্রুততা নিয়ে কাজ করে তাই এটা সত্ত্বই প্রয়োগ করা যেতে পারে সফটওয়্যার
ইন্ডাস্ট্রিগুলিতে।তাতে সফত্বারেগুলি হবে আরও আকর্ষণীয়।ধরা যাক আমরা একটা কোড
লেখলাম তা ১০০০ টি ডাটা নিয়ে কাজ করতে সময় নেয় ১ সেকেন্ড।এখন আমরা যদি এটা ডাবল
করে দেই তাহলে আমাদের অ্যালগোরিদম কতটা দ্রুত কাজ করতে পারে।এটা কি তখন একি সময়
নিবে নাকি এরথেকে ডাবল সময় নিবে নাকি চার গুন সময় বেশি নিবে।এটা আরও ভাল বোঝা
যায় যে আমরা একটা ওয়েব আপ্লিকাশন বানালাম যা ১০০ ব্যবহার করছে।এখন যদি ২০০ জন
ব্যবহার করে তাহলে এটা কতটা ভালভাবে কাজ করবে।এটা আমরা অ্যালগোরিদমের জটিলতা দিয়ে
বুঝতে পারব।তাই দেখা যাচ্ছে অ্যালগোরিদমের জটিলতা জানাটা আমাদের জন্য বেশ ভাল একটা
অপরিহার্য বিষয়।
এখন আমরা দেখি ছোট একটা কোড লেখব যা দিয়ে
আমরা গণনার কাজ করতে পারব।যা কিনা জাভাস্ক্রিপ্টে লেখা।
var M = A[0]; for(var i=0;i<n;++i){
if(A[i]>M){
M = A[i];
}
}
এখন দেখা যাক প্রসেসর কিভাবে এক্সিকিউট
করে।
১. ভালুগুলি ভারিয়াবলে
আসাইন করবে
২. এখন প্রতিটি ইলিমেন্ত অ্যারেতে খোঁজ
করবে
৩. দুইটা ভালু কম্পেয়ার করবে
৪. ভালু বৃদ্ধি করবে
৫. কিছু বাসিক গাণিতিক কার্যকলাপ
করবে।যেমন যোগ বা বিয়োগ
এখন, var M = A[0];
এটার জন্য দুইটা কাজ করা দরকার।একটা A[0] ও অন্যটা M এ ভালু আসাইন করা।এই দুইটি ব্যাপার এই
অ্যালগোরিদমের জন্য সব সময়ের জন্য দরকার(আমরা ধরে নিচ্ছি যে n সবসময় সর্বনিম্ন ১ হবে)।ফর লুপ কোডটিও সবসময় চলবে।এটা আমাদের আরও দুইটি
ইন্সট্রাকশন দেয়।সেগুলি হল
i = 0;
i
< n;
এই দুটি কাজ হয় লুপের প্রথম রান
টাইমে।তারপর প্রতিবার লুপ চলার সময় নিচের বিষয়গুলি কাজ করে
++ i;
i < n;
তাঁর মানে এইখানে মোট ইন্সট্রাকশন 4+2n ।চারটা লুপের কাজ শুরুর আগে আর দুইটা প্রতিবার
লুপের কাজ হলে।এখানে আমরা একটা গাণিতিক জিনিষ ব্যবহার করতে পারি। f(n) যেখানে n ইন্সট্রাকশন এর গণনা করে।তাহলে আমরা দেখতে পাচ্ছি
শূন্য ফর লুপের জন্য f(n)=4+2n.
Worst-case
analysis:
এখন লুপের ভিতরে দেখা যাক if(A[i] > M){ M =
A[i]
এইখানে দুইটি ইন্সট্রাকশন কাজ করে।একটি
অ্যারে চেক আর একটা আসাইন।এখন আমরা খুব সহজে f(n) কে লেখতে
পারিনা।কারণ এটা শুধু n এর উপর নির্ভর করেনা।ইনপুট ভালুর উপরও নির্ভর
করে। কারণ A = [1,2,3,4] নিশ্চিত A = [4,3,2,1] থেকে বেশী ইন্সট্রাকশন নিবে।এই যে সবচেয়ে বেশীবার
ইন্সট্রাকশন দরকার হচ্ছে।এটাকেই কম্পিউটার বিজ্ঞানীরা Worst case analysis বলেন।এইখানে যেটা হল
f(n) = 4+2n+4n
=6n +4.
এই ক্ষেত্রে আমরা দ্রুবকগুলি বাদ দিব।কারণ
ইন্সট্রাকশন বাড়ার সাথে সাথে 4 দ্রুবক থাকবে কিন্তু n দ্রুত বাড়বে।তাই এটার উপরই নির্ভর করবে অ্যালগোরিদমের জটিলতা।
f(n) =
n^2+3n+11;এইখানে আমরা f(n) = n^2 ধরে নিব।একি ভাবে f(n)=n+root(n); f(n) = n;
জতিলতাঃ
এখন একটা php কোড দেখা যাক
<?php
$exists = false;
for ( $i = 0; $i < n; ++$i )
{
if ( $A[ $i ] == $value ) {
$exists = true;
break;
}
}
?>
এইখানে দেখা যাচ্ছে f(n)=n. যদি এটা ১ থেকে n পর্যন্ত চলে।যদিও
এটা যেকোনো সময় ব্রেক হয়ে যেতে পারে।কিন্তু আমরা এখন সেটা দেখব না।কারণ আমরা Worst case নিয়ে কাজ করছি।
এখন কোড যদি হয়
এইরকম তাহলে
int i;
for ( i = 0; i < n; ++i ) {
f( n );
}
এইখানে বলা যায় f(n) = n^2.কারণ লুপের জন্য n আর ফাংশনটি n বার কল হবে তাই।
আমরা জানি যে O(1) (যেমন,v = a[ 0 ] + a[ 1 ];) একটি দ্রুবক,O(n)লিনিয়ার,O(n^2) quadratic এবং O(log(n)) লগারিদমিক।
লগারিদমঃ
লগারিদম ব্যাপারটি
অ্যালগোরিদমের জটিলতা বের করতে বেশ ব্যবহার করা হয়।কারণ এটা খুব তাড়াতাড়ি চলে আসে
জটিলতা নির্ণয়ে।খুব সহজে বলতে গেলে বলা যায় যদি কোন সংখ্যার উপর লগারিদমকে প্রয়োগ
করা হয় তখন সংখ্যাটি খুব ছোট হয়ে আসে। ঠিক যেমনটি আসে বর্গমূল নির্ণয়ের বেলায়।যেমন
2^x
= 1024
এখন আমরা একে x এর জন্য সমাধান করতে
চাইলে কি হয় যখন আমরা ভিত্তি রাখতে চাই ২।এটা আসলে ১০।কারণ 2^10 = 1024.এটাকে আমরা বলতে
পারি log(1024).আমরা জানি যে লগের
ভিত্তি বিভিন্ন হতে পারে কিন্তু আমরা শুধু চিন্তা করব ২ কে।
রিকারসিভ জতিলতাঃ
আমরা নিচের কোডটি দেখি
Int factorial( n ){
if (n == 1)
return 1;
return n * factorial( n - 1 );
}
এইখানে কোন একটি
সংখ্যার ফাক্তরিয়াল বের করা হচ্ছে।এইখানে দেখা যায় f(n) = n.কারণ এটি n সংখ্যক বার একজিকিউট
হবে।বুঝতে না পারলে হাতে হাতে গুনে দেখ।n=3 হলে কি হয়।তাহলে
দেখা যাচ্ছে এটি একটি লিনিয়ার সময় নিচ্ছে।
লগারিদমিক জতিলতাঃ
আমরা বাইনারি সার্চ
এর কোডটি দেখলেই বুঝব এটি মাঝের একটি সংখ্যাকে নিয়ে অ্যারেকে দুইভাবে বিভক্ত
করে।যদি সেই সংখ্যাটি হয় তাহলে শেষ আর যদি ছোট বা বড় হয় তাহলে ডানে ও বামে চলে যায়।এইভাবে
অ্যারেকে বার বার ভাগ করতে থাকে।এটাকে আমরা নিচের মতো করে দেখতে পারি
0th iteration: n
1st iteration: n / 2
2nd iteration: n / 4
3rd iteration: n / 8
...
ith
iteration: n / 2^i
...
last
iteration: 1
এখন আমরা ith ইটারেশনের দিকে
তাকালে দেখা যাবে অ্যারেতে n/2^i সংখ্যক সদস্য আছে।কারণ প্রতিটি ইটারেশনে অ্যারেকে
দুইভাগে ভাগ করা হচ্ছে।তাঁর মানে আমরা অ্যারে এলিমেন্তকে দুই দিয়ে ভাগ করছি।অন্যভাবে
বলা যায় ভাগফলকে দুই দিয়ে গুন করছি।আর এভাবে করতে থাকলে I সংখ্যক বারের জন্য
আমরা পাব n/2^i.এই পদ্ধতি চলতেই
থাকবে যতক্ষণ না অ্যারেতে ১ টি সংখ্যা থাকবে।এখন যদি আমরা জানতে চাই কতটি ইটারেশন
সম্পূর্ণ হয় তাহলে আমাদের নিচের সমীকরণটি সমাধান করতে হবে।
1
= n/2^i
এটা তখনই সম্ভব হবে
যখন আমরা ফাইনাল binarySearch() ফাংশনে পৌঁছে যাব।দুই
পক্ষকে 2^i
দিয়ে গুণ করে পাই
2^i
= n
এখনতো লেখায় যায়
i
= log(n)
| 
