Đánh Giá độ Phức Tạp Của Hàm Selection Sort

Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn PhícloseBạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn Phí

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG

Đánh giá độ phức tạp của hàm Selection Sortpower_settings_newLogin to reply3 postershome Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn Phí :: Thảo luận môn học :: Thông báo và hỏi đáp

descriptionĐánh giá độ phức tạp của hàm Selection SortWed Sep 29, 2010 8:04 pm

more_horiz

Code:

void SelectionSort(int A[],int n) { int min; for(int i=0; i<n-1; i++) { min = i; for(int j=i+1; j<n; j++) if(A[min]>A[j]) min = j; if(min != i) Swap(A[i],A[min]); }}Trong hàm Selection Sort, có gọi thủ tục Swap ta dễ thấy rằng hàm Swap có 3lệnh gán nên thời gian thực hiện là O(1).Trong Selection Sort lệnh gọi Swap nên chỉ tốn O(1), dòng for thứ 2 thực hiện n-i lần, mỗi lần thực hiện tốn O(1) nên tốn O (n-i) và đây cũng là độ phức tạp của hàm:T(n) =∑_(i=1)^(n-1)▒(n-i) = (n(n-1))/2 = O(n^2) thumb_upLikethumb_downDislikeduongvandeoit1k10Nhập mônTổng số bài gửi : 11Points : 17Join date : 16/09/2010keyboard_arrow_down

descriptionĐánh giá độ phức tạp ham Insertion sortWed Sep 29, 2010 11:35 pm

more_horizBài tập nhóm hai:

Code:

void Insetion sort (int a[], int n){1. for (int i=1; i< 0; i++)2. for (int j=i; j>0; j--)3. if (A[j]<a[j-1])4. swap (A[j],A[j-1]); } Câu lệnh (4) thực hiện O(1) câu lệnh (3) thực hiện O(1), cả hai câu lệnh thực hiện O(1+1)=O(1) Câu lệnh (2) thực hiện 1 lần Câu lệnh (1) thực hiện n-1 lần T(n)=∑i=1+2+…..+n-1=[n(n-1)]/2Vậy độ phức tạp của thuật toán là O(n^2)thumb_upLikethumb_downDislikephamthanhkhoiNhập mônTổng số bài gửi : 7Points : 7Join date : 15/09/2010keyboard_arrow_down

descriptionNhập Xuất Đa Giác n đỉnhWed Sep 29, 2010 11:42 pm

more_horiz

Code:

#include<stdio.h>#include<conio.h>int SoDiem;typedef struct{ int x; int y;}Diem;//Nhap diemvoid Nhap(Diem diem[],int SoDiem){ for(int i=1;i<=SoDiem;i++){ printf("Nhap diem thu %d \n",i); printf("Nhap x= \t"); scanf("%d",&diem[i].x); printf("Nhap y= \t"); scanf("%d",&diem[i].y); }}//Xuat diemvoid Xuat(Diem diem[],int i){ printf("x= %d\t",diem[i].x); printf("y= %d\t",diem[i].y);}//Tim hoanh do lon nhatint Max_x(Diem diem[20]){ int max; for(int i=1;i<=SoDiem;i++){ if(diem[i].x>diem[i-1].x) max=i; else max=i-1; } return max;}//Tim tung do lon nhatint Max_y(Diem diem[20]){ int max; for(int i=2;i<=SoDiem;i++){ if(diem[i].y>diem[i-1].y) max=i; else max=i-1; } return max;}void main(){ Diem diem[20]; int t; printf("So diem can nhap "); scanf("%d",&SoDiem); Nhap(diem,SoDiem); printf("Diem co hoanh do lon nhat la:\n"); Xuat(diem,Max_x(diem)); printf("\nDiem co tung do lon nhat la:\n"); Xuat(diem,Max_y(diem)); printf("\nDiem can tim: "); scanf("%d",&t); Xuat(diem,t); getch();}thumb_upLikethumb_downDislikephamthanhkhoiNhập mônTổng số bài gửi : 7Points : 7Join date : 15/09/2010keyboard_arrow_down

descriptionRe: Đánh giá độ phức tạp của hàm Selection SortMon Oct 04, 2010 12:48 pm

more_horiz

duongvandeoit1k10 đã viết:

Code:

void SelectionSort(int A[],int n) { int min; for(int i=0; i<n-1; i++) { min = i; for(int j=i+1; j<n; j++) if(A[min]>A[j]) min = j; if(min != i) Swap(A[i],A[min]); }}Trong hàm Selection Sort, có gọi thủ tục Swap ta dễ thấy rằng hàm Swap có 3lệnh gán nên thời gian thực hiện là O(1).Trong Selection Sort lệnh gọi Swap nên chỉ tốn O(1), dòng for thứ 2 thực hiện n-i lần, mỗi lần thực hiện tốn O(1) nên tốn O (n-i) và đây cũng là độ phức tạp của hàm:T(n) =∑_(i=1)^(n-1)▒(n-i) = (n(n-1))/2 = O(n^2)

===============================================Thầy ơi sao thầy hông cho nhận xét bài làm của em vây? Em làm thế có đúng không ạ?thumb_upLikethumb_downDislikeduongvandeoit1k10Nhập mônTổng số bài gửi : 11Points : 17Join date : 16/09/2010keyboard_arrow_down

descriptionRe: Đánh giá độ phức tạp của hàm Selection SortWed Oct 06, 2010 4:39 pm

more_horiz

duongvandeoit1k10 đã viết:

Code:

void SelectionSort(int A[],int n) { int min; for(int i=0; i<n-1; i++) { min = i; for(int j=i+1; j<n; j++) if(A[min]>A[j]) min = j; if(min != i) Swap(A[i],A[min]); }}Em làm bài này vầy nè thầy xem có đúng không thầylenh Swap= O(1)lồng trong lệnh if ma if cũng O(1) nên 2 câu lệnh bằng O(1).if va min cung bang O(1)for thi bằng O(n-i-1)lồng trong dòng for cua i ma for cua i = O(n-1)T(n)=O((n-i-1)*(n-1))=O(n^2-in-2n+i+1). Mà i đi đến n-2 nên T(n)=O(n^2-n(n-2)-2n+n-2+1)=O(n-1)Vậy đúng không thầy.

thumb_upLikethumb_downDislikelanhuongit2k10Nhập mônTổng số bài gửi : 14Points : 32Join date : 15/09/2010Age : 33Đến từ : Vĩnh Longkeyboard_arrow_down

descriptionRe: Đánh giá độ phức tạp của hàm Selection Sort

more_horiz Sponsored contentkeyboard_arrow_downadd_circleSimilar topicsremove_circleSimilar topicschat_bubbleĐánh giá độ phức tạp của X lũy thừa n (nhóm 6)chat_bubbleĐánh giá độ phức tạp của thuật toán Heap Sort ( Nhóm 4)chat_bubbleDanh gia do phuc tap cua thuat toan Quick Sort (nhom 3) chat_bubbleThuật toán Selection Sortchat_bubbleThầy cho em hỏi về đánh giá độ phức tạp!!!!!!Chuyển đến:Chọn Diễn Đàn||--Tiếng Anh Tiểu Học| |--Smart Start Grade 1 - Tiếng Anh lớp 1| |--Smart Start Grade 2 - Tiếng Anh lớp 2| |--Smart Start Grade 3 - Tiếng Anh lớp 3| |--Smart Start Grade 4 - Tiếng Anh lớp 4| |--Smart Start Grade 5 - Tiếng Anh lớp 5| |--My Phonics Grade 1 - Tiếng Anh lớp 1| |--Công nghệ thông tin| |--Học chuyên đề Online| | |--ASP NET MVC 3| | | |--Phân tích thiết kế hệ thống| | |--Bài tập phân tích| | | |--Lập trình căn bản C| | |--Các lệnh có cấu trúc & chương trình con| | |--Mảng một chiều| | |--Mảng hai chiều| | |--Ngôn ngữ hệ thống trong C| | |--Tài liệu môn học| | | |--Lập trình nâng cao| | |--Một số thuật toán sắp xếp| | |--Đại số ma trận| | |--Đệ quy| | |--Đánh giá độ phức tạp| | |--Đồ thị và thuật giải| | |--Phương pháp tìm nghiệm gần đúng| | | |--Lập trình hình thức và tính toán| | |--List and Matrix| | |--Lệnh điều khiển và vòng lặp| | |--Hàm tự định nghĩa| | |--Lập trình đệ quy với Maths| | |--Đồ họa 2D và 3D| | | |--Trí tuệ nhân tạo| | |--Phương pháp tìm kiếm Heuristic| | |--Phương pháp biểu diễn tri thức| | | |--Kế toán tin học| |--Lập trình đồ hoạ| |--Cơ sở dữ liệu| |--Hợp ngữ và lập trình hệ thống| | |--Ngắt 10h| | |--Ngắt 16h| | |--Ngắt 21h| | |--Ngắt 27h| | |--Ngắt 33h| | | |--Dot Net| | |--Share Point| | |--MVC 3| | |--C Sharp| | |--Linq| | |--Silverlight| | | |--Cấu trúc dữ liệu| | |--Kiểu dữ liệu có cấu trúc| | |--Kiểu dữ liệu trừu tượng| | |--Cây| | |--Tập hợp| | |--Đề tài tiểu luận| | | |--Thiết kế Web| |--Bảo mật thông tin| | |--Cài đặt thuật toán| | |--Bài tập mã hóa| | | |--Mạng| | |--Mạng căn bản| | |--Quản trị mạng| | |--Mạng nâng cao| | |--Bảo mật mạng| | |--Lập trình ứng dụng mạng| | | |--Olympic Tin Học SV-HS| |--Phương pháp toán cho tin học| |--Ngoại ngữ| |--Grammar| |--Listening| |--Writing| |--Reading| |--Dictionary| |--Ôn thi cao học| |--Môn tin| |--Môn toán| |--Sách - Tài liệu tham khảo| |--Lập trình C, C++| |--Kỹ thuật lập trình| |--Dot net| |--Cơ sở dữ liệu - Phân tích thiết kế - CNPM| |--Mạng| |--Toán học| |--Luận văn - Đồ Án| |--Khác| |--Kết nối| |--Thông tin công nghệ| |--Games| |--Nhân Tài| |--Một phút cuộc sống| |--Trao đổi kinh nghiệm| |--Thảo luận môn học| |--Thông báo và hỏi đáp| |--Ngân hàng đề thi các khóa| |--Hỗ trợ sinh viên |--Gia sư Dạy Kièm |--Việc làm gia sư |--Rao vặt |--Giải pháp Alpha |--Hoạt động gia sư Alphaprivacy_tip Permissions in this forum:Bạn không có quyền trả lời bài viếtpower_settings_newLogin to reply

• arrow_upward
• Trang Chính
• Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất

• Gia sư Alpha Vlog