01/10/2018, 14:03
Thuật toán tối ưu cho bài toán đếm
Bài này em giải với T(n^3), chắc chắn là quá thời gian . Mong các anh/ chị giúp em để có 1 thuật toán tối ưu … Em cảm ơn
Bài liên quan
Tác giả nổi bật
Từ khóa nổi bật
AngularJS
Blog
Bootstrap
C / C++
Cấu trúc dữ liệu & Giải thuật
Cơ sở dữ liệu
Codeigniter
Công cụ lập trình
CSS
CSS cơ bản
CSS3
Học Excel
HTML
HTML cơ bản
HTML5
Java
Javascript
jQuery
Json
Lập trình mobile
Laravel
Linux
MongoDB
MySQL
NodeJS
Oracle
Pascal
PHP
PHP cơ bản
PHP nâng cao
Python
React Native
ReactJS
Ruby
SEO
SQL Server
Swift
Visual Basic
VueJS
WordPress
XML
Chủ đề nổi bật
- 1 Cài đặt phần mềm cần thiết cho học lập trình web
- 2 Tự Học HTML Cơ Bản Online Miễn Phí Từ A đến Z
- 3 Seo website dành cho dân IT
- 4 REACT NATIVE
- 5 sdfdsf
- 6 Lập trình di động với React Native
- 7 Vue.js
- 8 Kiếm thức cơ bản HTML CSS
- 9 So sánh count() và sizeof() 2 phần tử đếm mảng
- 10 Toán tử và biểu thức của php
0
log(n^3)là3log(n)rồi còn gì nữa TLE thế [spoiler]*éo[/spoiler] nào đượcLấy bất kì 2 thanh gỗ từ 2 bộ đầu tiên, rồi kiểm tra xem thanh gỗ còn lại có số đo bao nhiêu. Kiểm tra xem trong bộ thứ 3 có thanh gỗ nào có chiều dài như vậy không.
Độ phức tạp O(n^2 log n).
Hi JustTee_Phương Ly.
Bạn có thể xắp xếp một loại sau đó dùng tìm kiếm nhị phân để giản thời gian tim thanh gỗ thứ 3.
Thực ra chỉ cần theta(n^2) thôi sắp xếp cả 3 mảng xong rồi giữ a, chọn b, dịch cửa sổ trong c. Tương tự cho hai lượt còn lại.