সন্নিবেশ সাজানোর সময় জটিলতা কি?
সময় জটিলতা ইনপুট পরিমাণের ফাংশন হিসাবে প্রক্রিয়া বা চালানোর জন্য কোড বা অ্যালগরিদমের একটি সেট দ্বারা নেওয়া সময়ের পরিমাণ।
সন্নিবেশ বাছাইয়ের জন্য, সময়ের জটিলতা হল O(n) ক্রম অর্থাৎ সেরা ক্ষেত্রে n-এর বড় O। এবং গড় বা সবচেয়ে খারাপ পরিস্থিতিতে জটিলতা হল O(n 2 ) ক্রম )।
নিম্নলিখিত ফর্মের n আকারের অ্যারেতে সন্নিবেশ সাজানোর অ্যালগরিদম প্রয়োগ করা হলে সাজানোর সময় জটিলতা কী হবে:6, 5, 8, 7, 10, 9 …… I, i-1
উপরের অ্যারে সাজানোর সময় জটিলতা হল O(n)। আসুন এই অ্যালগরিদমটি সাবধানে দেখি, এখানে সমস্ত জোড়া তাদের আসল অবস্থান থেকে অদলবদল করা হয়েছে অর্থাৎ উপাদান 1 এবং উপাদান 2 এর অবস্থানগুলি বিনিময় করা হয়েছে, 3 এবং 4 বিনিময় করা হয়েছে ইত্যাদি। সুতরাং, অ্যালগরিদম সাজানোর সময় এই অ্যালগরিদমটি সাজানোর জন্য শুধুমাত্র একটি অপারেশন n বার লাগবে৷
সন্নিবেশ সাজানোর সংজ্ঞা দিন এবং সন্নিবেশ সাজানোর জন্য একটি কোড লিখুন?
সন্নিবেশ বাছাই হল একটি সাজানোর অ্যালগরিদম যা একটি সাজানো অ্যারেতে উপাদানটিকে তার অবস্থানে রেখে ডেটা কাঠামো সাজায়৷
নিচের কোডটি সন্নিবেশ সাজানোর ফাংশন দেখায় -
উদাহরণ
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++){
int element = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > element){
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = element;
}
} 